I have been running into the same problem while trying to update my 5.3 CentOS machine.
Yum reported three packages that needed update :
java-1.6.0-openjdk x86_64 1:18.104.22.168-1.2.b09.el5 updates 27 M libxml2-python x86_64 2.6.26-22.214.171.124 updates 713 k python x86_64 2.4.3-24.el5_3.6 updates 5.9 M
yum update was issued however, the same error message kept popping up.
--> Missing Dependency: /usr/lib64/python2.4 is needed by package libxslt-python-1.1.17-2.el5_2.2.x86_64 (installed)
I tried disabling almost all my repositories, I removed many packages, almost ended up un-installing half my entire and then I googled on it. As always,, the answer was right there in front of me. Frank Cox wrote on the CentOS mailing list:
yum clean all yum update
And that works. Thank you Frank.