AHA!
Foi porque eu instalei o python2.7 ao lado do sistema python2.6 (seguindo esta grande página ). Eu tive que ser cuidadoso ao referenciar o python certo ( veja isso ) e deste descobri o meu problema: python27-devel
em vez de python-devel
foi necessário. Ah, ignorância.
Aqui está a última coisa que eu corri.
sudo yum install mysql mysql-devel mysql-libs
sudo yum install python27-devel
sudo yum install MySQL-python
sudo pip install mysql-python