I also have the same problem with my RedHat 7.2 and jre1.3.1_01
I've tried with PATH and CLASSPATH set to /usr/local/java/jre1.3.1_01/lib.
I've put e set -x in the LimeWireLinux.bin shell & seen that the right value are put.
Maybe there anything special to do during jre setup ??