Ok, então, por qualquer motivo, você tem um pacote python
em seu cache de pacotes local que fornece o Python 3, embora deva ser o Python 2.
Se você não tiver estragado muito ainda e apt-get
ainda funcionar, tente executar isto:
sudo apt-get install python=2.7.3-0ubuntu2.2 python3
e remova seus pacotes em cache com
sudo apt-get clean
depois.
Depois que tudo foi corrigido novamente, você provavelmente também deve verificar seu /var/log/apt/history.log
e ver quais pacotes foram removidos quando você desinstalou python3
anterior (o que você não deveria ter feito) e reinstalá-los novamente.