Why do I get "command not found" when the binary file exists?

Here's my problem. I have just compiled a linux build of tests in my VirtualBox VM. When I run it, I get:

bash: ./tests: No such file or directory

I did some research, and found it could permissions, missing libraries or different architecture. So I checked those:

• ls -al tests:

  -rwxr-xr-x 1 me me 9948598 2011-02-21 01:54 tests
  

• file tests

  tests: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.15, not stripped
  

• uname -a

  Linux DevBox 2.6.35-25-generic #44-Ubuntu SMP Fri Jan 21 17:40:44 UTC 2011 x86_64 GNU/Linux
  

• ldd tests:

  linux-vdso.so.1 =>  (0x00007fff7db90000)
  libpthread.so.0 => /lib/libpthread.so.0 (0x00007f10ef14c000)
  libstdc++.so.6 => /usr/lib/libstdc++.so.6 (0x00007f10eee46000)
  libz.so.1 => /lib/libz.so.1 (0x00007f10eec2d000) 
  libm.so.6 => /lib/libm.so.6 (0x00007f10ee9aa000)
  libc.so.6 => /lib/libc.so.6 (0x00007f10ee627000)
  /lib/ld64.so.1 => /lib64/ld-linux-x86-64.so.2 (0x00007f10ef384000)
  libgcc_s.so.1 => /lib/libgcc_s.so.1 (0x00007f10ee410000)
  

What's the problem here?

Take a look at this: https://stackoverflow.com/questions/1562071/how-can-i-find-which-elf-dependency-is-not-fulfill