How to fix "python installation is corrupted"?

My problem turned out to be solely due to an altered /usr/bin/python symlink as suggested in the error message. I was using update-alternatives with /usr/bin/python so it was pointing to /etc/alternatives/python. Turned out that do-release-upgrade is really strict with this symlink and merely selecting python2.7 with update-alternatives isn't enough, so I ended up forcing it to its original state:

sudo ln -sf /usr/bin/python2.7 /usr/bin/python

And that solved the problem.

If this doesn't work for you, then I guess you have a genuinely corrupted python install. I'd suggest

sudo apt-get install --reinstall python

this one is correct:

sudo update-alternatives --remove-all python
sudo ln -sf /usr/bin/python2.7 /usr/bin/python