Passei duas semanas procurando essa solução e depois que encontrei, decidi divulgá-la.
Não sei se aconteceu com todos, mas há cerca de três meses o plugin java do firefox foi automaticamente bloqueado, em virtude de ter sido descoberto na época uma falha de segurança no plugin da oracle. A solução foi substituir o pacote oracle pelo OpenJDK.
Ocorre que, agora, com a necessidade de se instalar o aplicativo da receita federal (agora disponível em .deb, podendo ser facilmente instalado pela central de programas do ubuntu, site da receita
http://www.receita.fazenda.gov.br/PessoaFisica/IRPF/2013/declaracao/download-programas.htm), o aplicativo Receitanet não instalava, pois aparecia uma mensagem de erro de dependência, que acusava a falta do java-virtual-machine.
A solução primária, recomendada em diversos sites e blogs era fazer a instalação do receitanet pelo dpkg -i e depois completar a dependência com apt-get -f install, tendo antes adicionado o repositório da oracle. No entanto, como não sei se o problema de segurança foi resolvido, não acredito que isso fosse o ideal.
No meu caso, essa solução resolveu momentaneamente o problema, mas criou outro: na atualização de sistema seguinte, apareceu uma mensagem de erro, que recomendava a atualização da distribuição para ser solucionada (o que eu não desejo).
Então, removi completamente o pacote java da oracle para estabilizar isso, o que acabou resultando na remoção do receitanet.
Pesquisando uma maneira de usar o receitanet com o OpenJDK acabei encontrando uma alternativa em
http://sinapseslivres.com.br/2012/02/imposto-de-renda-irpf-no-linux/A questão é que o OpenJDK, por padrão, não instala o dependência necessária para funcionamento do receitanet e se pesquisar dependências relacionadas no synaptic ou central de programas, não encontramos nada, porque o pacote em questão não está diretamente relacionado. Trata-se do gcj-jre-headless, que satisfaz da dependência virtual machine do pacote OpenJDK 7.
Instalando ele pelo synaptic ou central de programas do ubuntu, ou simplesmente executando:
sudo apt-get install gcj-jre-headless
Feito isso, o receitanet poderá ser instalado com facilidade pela central de programas.