Bueno, aca esta el ultimo error que recibi: http://pastebin.com/sC3BEKyy (Lo paso a pastebin, ya que soporta coloreado de sintaxis)
Lo solucione bajando la ISO de instalacion, removiendo yum, yum-fastestmirror y elementree
rpm -e python-elementtree-1.2.6-7.el4.rf.x86_64 yum yum-fastestmirror-1.1.16-14.el5.centos.1.noarch
Como no arrojo ninguna advertencia mas de dependencias, los instale desde la imagen montada
root@xxx# rpm -i /media/CentOS/yum-3.2.22-33.el5.centos.noarch.rpm /media/CentOS/yum-fastestmirror-1.1.16-14.el5.centos.1.noarch.rpm /media/CentOS/python-elementtree-1.2.6-5.x86_64.rpm
Luego ejecute yum para verificar que no tire ningun trace de python.. y salio andando.
Tiene CentOS algun sistema de rollback de upgrades? (bah.. existe en algun distro?)
Gracias por la ayuda, y ahora abro nuevo topic