Instale o eclipse do repositório e inclua o plug-in. Essa abordagem funcionou bem aqui. Recentemente tem havido muitos problemas com coisas estranhas em Java em 12.04.
Trabalho testado em 12.04 e 12.04.1
Veja também: Aptana não consegue encontrar o java
Essas são as etapas que funcionaram para mim no passado e ainda fazem.