Fedora uses rpm-packages. You install packages as an rpm, and the information about the package and installation is saved in the rpm-database. If you remove a package just by deleting the files the database doesn't know the package is removed. You should have removed the package with the rpm command. In a shell as root, execute:
rpm -e name_of_the_package
The name of the package is the name of the rpm you downloaded minus some suffixes. Always bit of a problem finding the name of the package. If rpm refuses to remove it because it's incomplete there must be a option to do it by force, just take a look at the man page by typing
I don't have rpm (I'm using debian, with debian packaging) so I can't help you any further than this. Succes.