O Sun Java foi movido para o repositório do Partner no Ubuntu 10.04 (Lucid Lynx).
Adicione o repositório fazendo isso:
add-apt-repository "deb http://archive.canonical.com/ lucid partner"
Então você pode fazer:
sudo apt-get update
sudo apt-get install sun-java6-jre sun-java6-plugin sun-java6-fonts