[linux] "No such file or directory" error when executing a binary

You get this error when you try to run a 32-bit build on your 64-bit Linux.

Also contrast what file had to say on the binary you tried (ie: 32-bit) with what you get for your /bin/gzip:

$ file /bin/gzip
/bin/gzip: ELF 64-bit LSB executable, x64-64, version 1 (SYSV), \
dynamically linked (uses shared libs), for GNU/Linux 2.6.15, stripped

which is what I get on Ubuntu 9.10 for amd64 aka x86_64.

Edit: Your expanded post shows that as the readelf output also reflects a 32-bit build.