Look at the permissions of the java binary, and make sure the read and execute bits are set. However, you will need to trace a couple of symlinks.
In my case I do the following:
ls -l `which java`
lrwxrwxrwx 1 root root 22 May 3 12:16 /usr/bin/java -> /etc/alternatives/java
ls -l /etc/alternatives/java
lrwxrwxrwx 1 root root 36 May 3 12:16 /etc/alternatives/java -> /usr/lib/jvm/java-6-sun/jre/bin/java
ls -l /usr/lib/jvm/java-6-sun/jre/bin/java
-rwxr-xr-x 1 root root 50794 Feb 2 17:25 /usr/lib/jvm/java-6-sun/jre/bin/java
Note that in my case, the read/execute bits are set for user, group, and other. If you are missing the "other" bits, you will be forced to use sudo. Remember that to execute a file, you must be able to read it: thus the read and execute bits. In my system's case, I would use the following command:
sudo chmod a+rw /usr/lib/jvm/java-6-sun/jre/bin/java
I like the wikipedia entry for the chmod
I hope that helps...