running a 64bit executable on a 64 ubuntu lucid

I have an ubuntu 10.04 64bit, and I'm trying to launch a 64 bit executable with no luck:

./lmrand1
-bash: ./lmrand1: No such file or directory    

ls -la lmrand1
-rwxr-xr-x 1 ysagon ysagon 191872 2011-09-05 18:13 lmrand1

file lmrand1
lmrand1: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked 
(uses sharedlibs), for GNU/Linux 2.6.9, stripped

I'm on a 64 bit ubuntu as well:

uname -a
Linux dev 2.6.32-33-server #72-Ubuntu SMP Fri Jul 29 21:21:55 UTC 2011 x86_64 GNU/Linux

The executable is not corrupted, I'm able to launch it on a redhat enterprise. Does someone know what is going on.

edit: sorry I have forgot to put the output of ldd

ldd lmrand1
    linux-vdso.so.1 =>  (0x00007fffabdff000)
    libpthread.so.0 => /lib/libpthread.so.0 (0x00007fe8d176c000)
    libm.so.6 => /lib/libm.so.6 (0x00007fe8d14e9000)
    libgcc_s.so.1 => /lib/libgcc_s.so.1 (0x00007fe8d12d1000)
    libc.so.6 => /lib/libc.so.6 (0x00007fe8d0f4e000)
    libdl.so.2 => /lib/libdl.so.2 (0x00007fe8d0d4a000)
    /lib64/ld-lsb-x86-64.so.3 => /lib64/ld-linux-x86-64.so.2 (0x00007fe8d19a4000)

Try installing the Linux Standard Base (lsb) package.

sudo apt-get install lsb