I have RH 7.1 and I'm trying to uninstall wu-ftpd. If i use gnorpm, it just crashes when i uninstall (I also can't verify packages) and if i do it from the command line, it says the package is not installed when I know it is!!! What the heck?

I dont know, but maybe the rpm database is corrupted.
maybe the rpm manual has an option to rebuild the database?

(Personally I stopped using rpm yrs ago, it's uncontrollable use of installer/uninstaller scripts from ppl I dont know doesnt suit my working methods, plus I get to deal with much more pre-compile options using tarballs making it more system specific.)