Consegui resolver o problema sozinho. O problema foi o symlink quebrado em /usr/bin
Primeiro eu identifiquei onde o python3 está. Eu imaginei que o binário python3 estaria em uma pasta similar a python2. Então eu digitei ls -l /usr/bin/python .
Isso me deu /usr/bin/python -> /etc/alternatives/python2.7 .
Como em /etc/alternatives/ não havia python3, eu repeti o processo
ls -l /etc/alternatives/python2.7 deu
/etc/alternatives/python2.7 -> /usr/bin/python2.7
Um simples ls /usr/bin/python* listou todos os binários do python disponíveis. O que me interessou foi python3.4 .
Então eu simplesmente criei um link simbólico com sudo ln -s /usr/bin/python3.4 /usr/bin/python3 .
Problema resolvido.