(In reply to Stephan Kulow from comment #1) > that sounds like your rpm database is somehow busted Very possibly true, but I'm looking for a solution. I'd suspect that the dependencies are not quite correct; at the worst, if the package can't be found, just install the new version (since not finding the old version is exactly the same as having successfully removed it).