Make sure that all the other binaries in need are executable as well. The p4v command is just a Bourne shell script that calls p4v.bin, and if that is not executable, it won't be found by the shell.
Key error that gives this away:
/usr/bin/p4v.bin: not found
To solve this problem, use chmod+x on p4v.bin, p4admin, p4admin.bin, p4merge, p4merge.bin, and p4vc.