As Smax says it sounds like you simply deleted the specific program folder under programs, which will not work. Unfortunately, the add/remove function now will not either since when it goes out to find a program to remove, it's already gone.
When a program is installed on a PC, parts and elements of that program are scattered in many locations, along with referenced in the registry. When you remove a program by brute force by simply deleting it's main folder, it's kind of like pulling up a weed but leaving all the roots behind. The references are still there so when a new installation is tried, it fails because it finds a reference to a newer version, even though the majority of the program is gone.
As CBFree4U has said, try Revo uninstaller. I have never used it as I have not encountered that situation, but at this point, it won't hurt and you have nothing to lose by trying it.
Thanks to Solar Wings for the special siggy.