YUM error - Package tuple (…) could not be found in rpmdb

Encountered this error When I was updating the kernel on one of the servers:

# yum update
Error: Package tuple ('nagios-plugin-all', 'x86_64', '0', '4.6.0', '6.fc15') could not be found in rpmdb

Tried remove the installed version and got the same error:

# yum erase nagios-plugin-all
Error: Package tuple ('nagios-plugin-all', 'x86_64', '0', '4.6.0', '6.fc15') could not be found in rpmdb

Tried skip this package and update the kerenl first then come back update the package, also got the same error. Googled a bit and turns out it is possible that I have a corrupted rpmdb. I had to:

# yum clean all
# cp -r /var/lib/rpm/__db* /root/rpmdb-bk/
# rm -rf /var/lib/rpm/__db*
# rpm --rebuilddb

to rebuild rpmdb and fix this issue.