you should try apt-get.
in a terminal window type in
sudo apt-cache search java
then look thru the results and find a java package.
then type in
sudo apt-get install (package name>
ill boot my kubuntu box and see what java packages there are. i have never installed in the past so we will see whats available.
also, switching to another distro may solve some probs, but create others. linux isnt for the faint of heart