Eu também tive esse problema, e a minha aposta é que a micro instância gratuita não tem RAM suficiente. A mesma instalação é executada muito bem em uma pequena instância.
Agora, não estou dizendo que esses 613 MB de RAM não são suficientes para executar o Java nessa instância. Acho que os pacotes do Ubuntu tentam iniciar a JVM com algum tamanho de heap grande e isso não se encaixa na instância.
A maneira como executo o Java em microinstâncias é instalar o JDK usando o pacote Sun (er ... Oracle). Obtenha aqui e execute a instalação você mesmo . Observe que você provavelmente precisará adicionar manualmente o binário java ao seu PATH.
Meu palpite sobre o tamanho do heap vem do fato de que a instância será interrompida da mesma maneira se eu instalar manualmente o Java e iniciar uma VM com um tamanho de heap enorme (digamos, 1 GB).
Boa sorte!