This is basically bug 89500 for RHEL. The issue is that RPM orders installations properly to satisfy dependencies, but erasures are not, which results in things like stray directories and uninstallation scripts failing. (Note that I'm not sure this is solved in Fedora's RPM either since CLOSED UPSTREAM when it comes to Jeff is probably means his rpm5.)
*** This bug has been marked as a duplicate of bug 448153 ***