O problema é que eu estava com o JRE errado, mesmo parecendo que tinha o caminho certo.
Instalar o Oracle JDK resolveu o problema:
Eu instalei o minecraft da maneira que eu deveria.
Quando inicializo o launcher, é o que recebo:
Bootstrap (v5)
Current time is Dec 6, 2015 9:52:08 PM
System.getProperty('os.name') == 'Linux'
System.getProperty('os.version') == '4.2.0-19-generic'
System.getProperty('os.arch') == 'amd64'
System.getProperty('java.version') == '1.7.0_91'
System.getProperty('java.vendor') == 'Oracle Corporation'
System.getProperty('sun.arch.data.model') == '64'
Looking for update
Downloading: https://s3.amazonaws.com/Minecraft.Download/launcher/launcher.pack.lzma
Got reply in: 800ms
No update found.
Unpacking /home/seph/.minecraft/launcher.pack to /home/seph/.minecraft/launcher.jar
Cleaning up /home/seph/.minecraft/launcher.pack
Starting launcher.
E então ele simplesmente fica pendurado aqui e tende a parar de responder após cerca de 30 segundos. Alguém já viu isso antes, ou alguém sabe como eu posso descobrir mais sobre o que está errado?
$ java -version
java version "1.7.0_91"
OpenJDK Runtime Environment (IcedTea 2.6.3) (7u91-2.6.3-0ubuntu0.15.10.1)
OpenJDK 64-Bit Server VM (build 24.91-b01, mixed mode)
Para mim, funcionou após a instalação do OpenJDK 8:
sudo apt-get install openjdk-8-jre
Não há necessidade de instalar o Orakle JDK.
(atualmente usando 15.10 64bit)