Seu caminho parece ok. Portanto, um primeiro tiro:
Reinstale o pacote original do Python via
sudo apt-get install --reinstall python
para substituir a instalação anterior.
Mas sua última edição (Edit 3) fornece a solução. Remova o binário em /usr/local/bin
via
sudo rm /usr/local/bin/python
ou renomeie o arquivo
sudo mv /usr/local/bin/python /usr/local/bin/python-2.5.4