Opa!
Ontem atualizei meu Ubuntu 9.10 pro Lucid Lynx, e hoje fui trabalhar no JahCaixa e TAN TAN TAAAN!!!
Parece que o JDK foi removido da distribuição 10.4, por isso ele removeu o que eu tinha instalado.
Pesquisando um pouco, parece que a solução é adicionar o Repositório Partner da Sun, onde o sun-java6-jdk está sendo distribuído.
Segue um link com mais detalhes.
http://beeznest.wordpress.com/2010/04/23/howto-install-suns-java-on-ubuntu-lucid-lynx-10-04/