I am using Red Hat 9 and having problems uninstalling a couple of rpm packages. If i use rpm -e, I get a message telling me the package is not installed, but if I try to reinstall it, I get a message saying the package is already installed. Nothing like a bit of consistency...

The install does actually run if I use -replacepkgs. However, I could really do with knowing why the uninstall is failing, as i want to try recompiling the app from source with a couple of extra options instead of simply accepting the rpm defaults.

Any ideas as to why I can't get rpm -e to work?

rpm and it's database are notorious.
Try a rpm --rebuilddb

Cheers,
Tink