Acabei de analisar mais algumas soluções e, finalmente, deparei com o seguinte que realmente resolveu o meu problema. Então eu pensei em postar no caso de alguém ter enfrentado o mesmo problema.
sudo rm /usr/bin/python3
sudo ln -s python3.5 /usr/bin/python3
Este foi um problema com as aplicações do sistema que já dependiam do python 3.5. O problema estava relacionado com o symlink python3.