Broken yum - yum hangs when trying to remove a package

I removed a package with yum "successfully" but was unable to reinstall it, as yum seemed to think it was already installed.

Check a package for corruption: rpm -Vv package

Remove a package from the rpm database:
rpm -e --justdb --nodeps package

Probably a good idea to yum clean all if you didn't already.