Provavelmente, você está recebendo problemas para reinstalar o python a partir do apt-get, porque a instalação do tarball criou os arquivos usados no python
Você pode baixar o pacote python e suas dependências, colocar todos os arquivos no mesmo diretório e usar o dpkg para instalar sobrescrevendo os arquivos existentes:
-
Para obter o pacote do requeride, você pode executar apenas
apt-get install python
apenas para obter a lista dos pacotes que o apt deve instalar. -
Para baixá-los, use o comando
apt-get download [paste here the list of the packages]
em uma pasta vazia -
E para instalar, use nesta mesma pasta:
dpkg --force-overwrite -i *.deb
Espero que funcione. Boa sorte.
Editar: Minha resposta não considerou essa edição. Você deve corrigir os problemas que você obteve com os pacotes libgnome * antes de tentar acima.