try this in a root terminal :)
rpm --rebuilddb
this sould repair it, good luck!
He said in his message that he did it already but it didn't work.
Michael, I'm sorry but I don't have any better suggestions than backups, if that doesn't work. One thing - make sure you have shut down all programs that access the db, in case one has a lock on it. Do a ps ax and check for yum, apt, up2date, all of those processes.
Rich
