@Booming mencionou em um comentário, que o OpenJDK9 é ainda beta e de fato desinstalando o OpenJDK9 e instalando o OpenJDK8 corrigiu todos os problemas.
Eu tive que apt-get purge
de todas as coisas Java e depois reinstalar o OpenJDK8 para que funcionasse:
$ sudo apt-get purge java
$ sudo apt-get purge openjdk
Em seguida, verifique se realmente desapareceu:
$ sudo update-alternatives --config java
E instalando novamente:
$ sudo apt-get install openjdk-8-jdk openjdk-8-demo openjdk-8-doc openjdk-8-jre-headless openjdk-8-source