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.