Is this a 32bit or 64bit linux system?
Below in the quoted area a few questions from Olivier. Please try to run the suggested comands on the binaries from the broken system and report the results.
possibly the library loader (/lib/ld-linux.so.2) is corrupt, or it is a
dangling symlink ? That could cause a 'no such file or directory' error.
what does 'file /bin/bash' report? what does `ldd /bin/bash` report?
does someone have a virtual machine which can be used to reproduce the
problem? (I've tried on Ubuntu 9.04 but I found no problems)