Use o RPM para reinstalar o pacote do Python 2.6. Isso deve redefinir todas as dependências e o rpm não depende do python.
Primeiro, obtenha uma cópia do Python rpm da mídia de instalação ou repositórios on-line oficiais do Red Hat ou CentOS.
No meu host do CentOS 6, o pacote é python-2.6.6-52.el6.x86_64. Seu pacote pode ser diferente com base na plataforma e no lançamento do SO.
sudo rpm -Uvh --replacepkgs python-package.rpm
Como você descobriu, geralmente é uma má idéia modificar os executáveis gerenciados pelo rpm. Existem várias discussões na Internet sobre a atualização do Python para o 2.7 no RHEL / CentOS. Você pode querer começar por aí.