Primeiro, você deve instalar o Java oficial. Instale openjdk-7-jre .
O pacote default-jre realmente não faz muito. Eu não acho que realmente faça nada.
Se isso não funcionar, verifique sua variável PATH e verifique se ela contém o caminho de instalação do Java. Você pode verificar onde ele está instalado executando dpkg-query -S 'openjdk-7-java*' e procurando pelo binário java. Geralmente é nomeado java e geralmente está em uma pasta bin . Adicione isso à variável PATH .