tenta instalar de novo o jdk
sudo apt-get install sun-java6-jdk
nunca tive problemas com isto
vc tbm pode baixar o binario com jdk+netbean (100mb mais ou menos) no site da sun, que tem a vantage de instalar o jdk e netbenas na tua pasta home(qualquer coisa é so apagar sem afetar o sistema)