Hay veces que necesitamos instalar la versión de Java de Oracle en vez del OpenJDK que las distribuciones Linux proporcionan por defecto. En Ubuntu es tan sencillo como añadir un ppa:

sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java7-installer
java -version

Nota:
si no está instalado el comando add-apt-repository, lo instalamos:

sudo apt-get install python-software-properties