Cannot find open shared object file libjli.so -- no such file or directory

On 64-bit RHEL5 running Java 1.6.0 update 16, root can successfully run a Java program but a user can't because libjli.so supposedly can't be found. SELinux is turned off and the environment is the same before the program is run. I've tried putting libjli.so in the LD_LIBRARY_PATH but it doesn't make a difference.

How do I fix this error?

The first possibility that springs to mind is that libjli.so is readable only by root. So step one:

ls -l $(locate libjli.so)

If it's in an odd location (not in /usr/lib or /lib) create the file /etc/ld.so.conf.d/java.conf containing the path to the directory containing libjli.so and run /sbin/ldconfig as root.

For more troubleshooting info, run this command, once as root and once as a non-root user:

ldd java

In a sane world, the output of the two would be identical. How they differ should tell you a lot about why this is failing.