While reading through this site, http://wilsonet.com/mythtv/fcmyth.php I saw this part and I think that this might be a very common problem for fc users. Just in case we got into this trouble:

After the big upgrade(yum -y upgrade), you MAY get an error about being unable to open the rpm database (this used to happen to me w/RHL9, but hasn't ever with FC). If you do encounter this error, try the following:

# rm -f /var/lib/rpm/__db*
# rpmdb -vv --rebuilddb

The database rebuild will take quite a while to complete. After it completes, you'll see an error message, but you can safely ignore it and move on to see if the rebuilddb cleared the problem. If not, good luck... Note that the presence of those __db* files doesn't indicate a problem, they're supposed to be there, they just get corrupted every once in a while.