I recently encountered this on my Fedora 10 machine. I looked and looked and found a bunch of advice that did not work. Among that advice was rebuild the RPM database, and clean the yum repository.
The answer though was I had a bad yum repository that I found by disabling all the yum repositories I had and re-enabling them 1 by one.
If you find this page b/c of the error above I suggest the same methodology for finding the offending repository.