Strange that this trouble is bad supported here.
Open up C:\Program Files\InstallShield Installation Information\{ECEBA21C-8607-40A7-AB90-9E929AA6CB20}
Right click on "setup.exe" and select Compatibility: Vista (any: SP1,SP2).
After that you'll be able to uninstall Workstation via this setup.exe.
I had ver.2.0.x, which was in that folder. If such folder doesn't exist - check other folders in Program Files\InstallShield ...\ for Parallels setup.exe.
