Is this a fairly recent development, say in the past week? I see a few other
threads with similar complaints (and I'm having the same problem) since the
last Vista update. Do a search on Uninstall here and look at some of those
threads. Folks are mentioning that some registry entries related to
uninstalling got wiped out or something along those lines.
Also, try installing something new and see if that piece of software can be
uninstalled afterwards.