I had the exact same problem mentioned at the beginning of this threat. None of the suggestions here solved my problem, but I did find the solution. I am posting my solution here for the benefit of others.

I installed the rpm version of j2re1.4.1_01. I found it makes no difference whether the rpm or tar.gz version is installed.

PATH in .bash_profile is set to:
PATH=/usr/java/j2re1.4.1_01/bin:$PATH

"which java" results in:
/usr/java/j2re1.4.1_01/bin/java

This shows PATH is correct.

However, "sh ./LimeWireLinux.bin" still failed.

It turned out there was a file:

/usr/bin/java

on my system. Although this was not the first java in my path, it was still executed by the Limewire installer. /usr/bin/java is a shell script. It turns out some of the errors produced when the Limewire installer fails are generated by this script. This proves /usr/bin/java is executed. I believe this must be a bug in the Limewire installer script

After I renamed /usr/bin/java out of the way (as root):

mv /usr/bin/java /usr/bin/java.orig

the Limewire installer worked fine.

On my system, /usr/bin/java is not owned by any rpm. It is there for compatibility was libgcj (part of gcc).

Some people mentioned they defined CLASSPATH in their .bash_profile. On my system this has no effect.