Just to ask, when you tried to install VMware Tools again, did you use the 'run as administrator' from the right click? Also, how up to date is the OS on the VMs in question? I don't recall if there are updates that (if present) could cause this.

IMO, if these are production VMs, and none of your attempts have resolved the issue pretty soon, I'd open a support incident to get it resolved before the next backup is scheduled to run.