You might want to type rpm -qa | grep <program-name> to get your program's package name.
rpm -qa lists all the rpm packages you have installed
| grep <program-name> looks in the list for your program name.
Let's say I want to uninstall RealPlayer. If I type rpm -e RealPlayer, rpm will say that I don't have it installed, even though I do.
So I type rpm -qa | grep RealPlayer and I get this line: RealPlayer-8.0-1
Then I type rpm -e RealPlayer-8.0-1 and it works! (Unless there are dependencies to uninstall as well)