Meu problema acabou sendo causado apenas por um link simbólico /usr/bin/python alterado, como sugerido na mensagem de erro. Eu estava usando update-alternatives com /usr/bin/python , então estava apontando para /etc/alternatives/python . Acontece que do-release-upgrade é realmente estrito com este link simbólico e simplesmente selecionar python2.7 com update-alternatives não é suficiente, então acabei forçando-o ao seu estado original:
sudo ln -sf /usr/bin/python2.7 /usr/bin/python
E isso resolveu o problema.
Se isso não funcionar para você, então eu acho que você tem uma instalação de python genuinamente corrompida. Eu sugeriria
sudo apt-get install --reinstall python