La risposta è in questa riga dell'output di readelf -a nella domanda originale
[Requesting program interpreter: /lib/ld-linux.so.2]
Mi mancava il file /lib/ld-linux.so.2, necessario per eseguire app a 32 bit. Il pacchetto Ubuntu che contiene questo file è libc6-i386.
Vecchia domanda, ma spero che questo aiuti qualcun altro.
Nel mio caso stavo usando una toolchain su Ubuntu 12.04 che è stata creata su Ubuntu 10.04 (richiede GCC 4.1 per essere compilata). Poiché la maggior parte delle librerie si è spostata su directory multiarch, non è stato possibile trovare ld.so. Quindi, crea un collegamento simbolico per questo.
Controlla il percorso richiesto:
$ readelf -a arm-linux-gnueabi-gcc | grep interpreter:
[Requesting program interpreter: /lib/ld-linux-x86-64.so.2] Crea collegamento simbolico:
$ sudo ln -s /lib/x86_64-linux-gnu/ld-linux-x86-64.so.2 /lib/ld-linux-x86-64.so.2
Se sei a 32 bit, sarà i386-linux-gnu e non x86_64-linux-gnu.