A instalação acima foi correta , obrigado à @Fuzzyfelt pela verificação.
Depois de muitas tentativas e tentativas frustradas com outra versão do Java, desisti e procurei na web (novamente) por dicas. Finalmente, me deparei com este post
O Strato (strato.de) tem erros em seu software de virtualização executando o Ubuntu 12.04 LTS com Java.
Mudando hoje para o Ubuntu 10.04 LTS e tudo bem!
Vou deixar este post aqui, a menos que alguém me dê um argumento razoável para excluí-lo. Deveria haver mais recursos na web apontando esse problema com o Ubuntu 12.04 LTS e o Java no Strato, até onde eu sei.