Por algunos extraños motivos que pueden leerse buscando un poco en
Google, Canonical ha decidido no tener en sus repositorios oficiales
el paquete de Sun para tener el JDK disponible, incluyendo el
cuestionado OpenJDK únicamente.

Para tener disponible los paquetes necesarios hay que añadir el
repositorio de socios:
#sudo add-apt-repository "deb http://archive.canonical.com/ lucid partner"

Fuente: http://ubuntronics.blogspot.com/2010/04/instalacion-de-java-6-jdk-en-ubuntu.html