This is how I fixed my problem. You may fix this by cleaning out rpm database. But first, in order to minimize the risk, make sure you create a backup of files in /var/lib/rpm/ using cp command: mkdir /root/backups.rpm.mm_dd_yyyy/ cp -avr /var/lib/rpm/ /root/backups.rpm.mm_dd_yyyy/ The try this to fix this problem: # rm -f /var/lib/rpm/__db* # db_verify /var/lib/rpm/Packages # rpm --rebuilddb # yum clean all And finally verify that error has gone with the following yum command # yum update