Felizmente para você, é um problema antigo, amplamente discutido. Há uma solução para esse aqui . Basicamente consiste em:
dpkg --remove --force-all python
dpkg --remove --force-all python2.6-minimal
Agora baixe os Pacotes Debian mais recentes (por favor, certifique-se de que as versões do pacote instaladas são as mais novas disponíveis para você, essas versões estavam ok em algum momento no passado, quando eu tive que fazê-lo) e execute:
dpkg --install --force-all python_2.7.1-0ubuntu5_all.deb
dpkg --install --force-all python-minimal_2.7.1-0ubuntu5_all.deb
apt-get clean
apt-get autoclean
apt-get update
apt-get install -f
Você pode fazer o script com facilidade e fazer o upgrade da versão a partir de um script.