Olá,
Mais uma tentativa:
Na tela inicial, (área de trabalho), digite Alt+F2. Na tela que aparecer digite "gksu nautilus".
Será aberta uma janela de navegação de arquivos, procure pela pasta (/usr/lib/jvm/). Dentro dela irão existir as pastas do java, delete todas elas.
Abra o Gerenciador de pacotes Synaptic, procure pelo java-sun, marque para desinstalação.
Ele vai tentar desinstalar, não vai encontrar os pacotes, e em função irá remover as referências.
Depois disto o java deverá estar desinstalado. Agora basta instala-lo novamente, para isto sugiro a utilização da Central de Programas Ubuntu.
Espero que funcione.