Eu estava tendo o mesmo problema no Ubuntu 11.10, tentei todas as mesmas soluções, nenhuma delas funcionou para mim também. Eu encontrei isso em outro fórum de discussão e parece ter funcionado para mim:
Se você quiser remover oracle-jdk7-installer, você pode simplesmente ir / var / lib / dpkg / info / Demora algum tempo para carregar e excluir todos os arquivos que começa com oracle-java7 ***** havia ~ 6files, então vá para Synaptic e simplesmente localize o mesmo oracle-jdk e clique em remove / complete remover.
Aqui é onde eu encontrei: link
Boa sorte!
Editar : aqui estão os 3 passos para fazer isso facilmente:
Abra um terminal (ctrl + alt + T) e digite os dois comandos sucessivamente:
cd /var/lib/dpkg/info/
sudo rm oracle-java7-installer*
Abra o synaptic, procure por "oracle-java7-installer", marque-o para remoção completa e clique em "apply".
Editar : Para aqueles que não possuem synaptic instalado, após você rm os arquivos do instalador do oracle, apenas faça:
sudo apt-get purge oracle-java7-installer
E você deve ser bom.
editar : trabalhei também no Ubuntu 12.04 LTS