No seu caso, você teve muita sorte de ter usado checkinstall
! Em vez de instalá-lo sem rodeios, sobrescrevendo / movendo arquivos, ele criou um pacote que foi instalado. Isso torna o gerenciamento de pacotes ciente da instalação e como desfazê-lo. Então, isso significa que você pode dizer ao APT que agora deseja instalar a outra versão:
Executar
sudo apt-get install python=2.7.4-0ubuntu1
para reverter para a versão padrão do pacote do Ubuntu. O Python 2.7.5 provavelmente estará disponível apenas no Saucy, não nas versões estáveis atuais.
Isto não é o mesmo que remover e reinstalar, já que neste caso ele é desclassificado, cuidando que uma única versão do Ubuntu esteja instalada o tempo todo.