Você precisa remover o comentário das duas linhas em /etc/apt/sources.list que se referem a "parceiro" Experimente:
sudo nano /etc/apt/sources.list
substitua "nano" pelo editor de texto instalado, como o vi etc.
descomente as duas linhas referindo-se a "parceiro", (remova o #)
Se não houver repositório, adicione um:
sudo add-apt-repository "deb http://archive.canonical.com/ maverick partner"
Agora,
sudo apt-get update
sudo apt-get install sun-java6-jre sun-java6-bin sun-java6-jdk