p4 - I've got no such file or directory - when in reality it exists

I have installed p4 command line client on the server, and something strange happened. It exists, has executable rights, but I cannot execute it beacause I got message that it does not exists.

I will put terminal commands and output to describe whole situation:

user@host:~$ echo $PATH 
/opt/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games

user@host:~$ which p4
/opt/bin/p4

user@host:~$ ls -l /opt/bin/p4
-rwxr-xr-x 1 root root 748840 2010-03-16 00:24 /opt/bin/p4

user@host:~$ file /opt/bin/p4
/opt/bin/p4: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.2.5, stripped

user@host:~$ ldd /opt/bin/p4
        not a dynamic executable

user@host:~$ p4
-bash: /opt/bin/p4: No such file or directory

user@host:~$ /opt/bin/p4
-bash: /opt/bin/p4: No such file or directory

user@host:~$ strace /opt/bin/p4
execve("/opt/bin/p4", ["/opt/bin/p4"], [/* 19 vars */]) = -1 ENOENT (No such file or directory)
dup(2)                                  = 3
fcntl(3, F_GETFL)                       = 0x8002 (flags O_RDWR|O_LARGEFILE)
fstat(3, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f58db339000
lseek(3, 0, SEEK_CUR)                   = -1 ESPIPE (Illegal seek)
write(3, "strace: exec: No such file or di"..., 40strace: exec: No such file or directory
) = 40
close(3)                                = 0
munmap(0x7f58db339000, 4096)            = 0
exit_group(1)                           = ?