Sometimes, for example if you kill the yum update process, the RPM database is left in an inconsistent state.
Here's how to fix that:
rm -f /var/lib/rpm/__db* db_verify /var/lib/rpm/Packages rpm --rebuilddb