La respuesta está en esta línea de la salida de readelf -a en la pregunta original
[Requesting program interpreter: /lib/ld-linux.so.2]
Me faltaba el archivo /lib/ld-linux.so.2, que se necesita para ejecutar aplicaciones de 32 bits. El paquete de Ubuntu que tiene este archivo es libc6-i386.
Pregunta antigua, pero espero que esto ayude a alguien más.
En mi caso, estaba usando una cadena de herramientas en Ubuntu 12.04 que se creó en Ubuntu 10.04 (requiere GCC 4.1 para compilarse). Como la mayoría de las bibliotecas se han movido a directorios de varias arquitecturas, no pudo encontrar ld.so. Así que crea un enlace simbólico para él.
Marque la ruta requerida:
$ readelf -a arm-linux-gnueabi-gcc | grep interpreter:
[Requesting program interpreter: /lib/ld-linux-x86-64.so.2] Crear enlace simbólico:
$ sudo ln -s /lib/x86_64-linux-gnu/ld-linux-x86-64.so.2 /lib/ld-linux-x86-64.so.2
Si está en 32 bits, será i386-linux-gnu y no x86_64-linux-gnu.