What annoys me about uninstalling software is that you never quite get rid of all it's components. I only realised this when after uninstalling and re-installing I was surprised to see all my settings were exactly the same. Anyway, a quick browse of your registry will prove the point - you'll see registry entries from software you thought long gone!
If you're happy with playing around with the registry, I'd uninstall the software, then manually delete all registry entries pertaining to it (start, run, regedit). Then reinstall and I bet everything is fine again.
Make sure you back up the registry first