Experimente primeiro o OpenJDK 7+ (disponível no repositório).
Se não estiver funcionando, tente
sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java8-installer
para instalar o oficial, o Java JDK . Você não deve precisar do primeiro comando como você já fez, mas isso é para referência futura.
A corrida:
sudo update-alternatives --config java
em que você pode escolher especificamente o Java JDK . Então tudo deve funcionar como esperado.
PS: na minha opinião, essa questão pertence aqui, pois é específica do sistema operacional e não está relacionada à programação per se . Quero dizer, você poderia ter substituído Java
com qualquer outro programa (bem, é a primeira vez em quando que vejo uma instalação tão complicada no Linux, acho que esse é o carma de Java;)