Désolé, j'ai lu trop vite. C'était pas /usr/bin/..., etc. , mais /usr/lib/...
Et ça ?
ls -lZ /usr/lib/{,x}python{2.7,3.3}
rpm -V python-libs python3-libs
Si ça ne donne rien, tu peux aussi essayer de réinstaller les paquages: python-libs, python3-libs (attention aux numéros de version, faut reprendre les mêmes qu'avant)