O problema foi que de alguma forma eu consegui instalar uma versão do ElasticSearch que requeria o Java 7 (openjdk-7- *) que não é compatível com o Ubuntu 11.04.
O motivo pelo qual eu quis atualizar é devido a uma vulnerabilidade que torna seu servidor utilizável para ataques de DDOS.
Eu finalmente consertei o problema fazendo downgrade do Elastic Search para a versão 1.1.2 e adicionando regras de firewall ao meu iptables.