I am getting the exact same problem with my VMWare Workstation 6.0.3 and 6.0.4 (the new release). I even downloaded the 6.5 beta and still got the same result on my Vista Ultimate x64 (AMD). As with the original poster, VMWare Player works just fine. I had uninstalled with Add / Remove program successfully and still ran the VMWare_Install_Cleaner utility without problems.
The only thing I did different was that prior to Vista SP1 my 6.0.2 worked just fine. Then I updated to SP1. Then I thought I'd update to VMWare Workstation 6.0.3 but then got the problem. Uninstalled, cleaned, then installed 6.0.4 and still got the problem. Then uninstalled, cleaned, then installed 6.5 beta and still got the same problem. And I performed reboots between installs.
EDIT: I probably didn't do a VMWare_Install_Cleaner before installing 6.5 because, after doing so, not only did the installation looked better in Process Monitor, Vista asked if I wanted to trust a couple of VMWare components (forgot which ones). After a reboot, it worked fine. Strangely, I wanted to check out the vminst.log but procmon said it was being written in C:\Users\<username>\AppData\Local\...vminst.log, which, I still couldn't find. Even when searching the entire c: drive.
Once again, just to say, the 6.5 beta worked.
EDIT2: For those not in the know. VMWare Workstation 6.5 beta runs in debug mode which can never be switched off (probably means a debug build). This also means that performance will be substantially slower than release versions. Also the VMWare Tools for windows guest OSes will need to be updated. So if you can deal with that, then by all means, use the beta.
