After a recent upgrade of a server from CentOS 4.4 to 5.1 using yum, I ran into a bit of a problem with rpm.
Pretty much any rpm command would result in the following error:
rpmdb: Program version 4.3 doesn’t match environment version
error: db4 error(-30974) from dbenv->open: DB_VERSION_MISMATCH: Database environment version mismatch
error: cannot open Packages index using db3 – (-30974)
error: cannot open Packages database in /var/lib/rpm

The solution as suggested on a Fedora forum was:
rm /var/lib/rpm/__db.*
rpm –rebuilddb
Once this had finished, everything was back to normal.