Sometimes the best way to uninstall an app is to REINSTALL it first. This will recreate the uninstall information that other cleaners (or manual attempts at removal) sometimes erase. You can then easily uninstall it through the Windows Add/Remove tool (Start->Run appwiz.cpl).

Note that this may not work unless you have the original install files (setup) for the same version as currently installed. Trying to install a later version may be disallowed without uninstalling the old one, which is the problem you're having. That's why I like to archive my install software to DVD after I upgrade to later versions, at least for the most important apps.

This won't always save you - I still have some machines on my network at the office that have old installations that can't be removed due to missing uninstall info. One of these is Windows Defender -- when the uninstall info was wiped it won't even allow itself to be reinstalled on top of itself, rendering this tip useless in this case. Fortunately it can be effectively disabled, since we're using another security app that makes Defender redundant.