Due to the persistent problem I'm having with one of my VMs which cannot access the internet, I decided to try uninstalling Parallels tools using the Add/Remove programs control panel applet (with the intention of then restarting and installing Parallels Tools again). For SEVERAL HOURS, it claimed that the time remaining is 5 minutes. I finally clicked cancel and it's been hourglassing at me for a good 15 minutes. Was this the wrong approach? And what should I do to fix this?
Run Parallels Tools install again from the menu, you see an option to remove Parallels Tools. That has worked better for me than using remove/add programs from Windows.