We are currently testing BE 2012 in a replicated testing environment of our production network (so we have the luxury to trash and re-install the product), we are also getting the same issue.
We have tried all the suggestions above, nothing is working, I have opened up a case with Symantec this morning and I am waiting for a technician call back.
We tried the solution that worked for someone in another KB (http://www.symantec.com/connect/forums/be2012-cannot-backup-powered-vmware-vm), removing completly the RAWS agent on our vCenter server and reinstalling it, same issue. We used the following procedure to ensure it was completly removed prior to re-installing (http://www.symantec.com/business/support/index?page=content&id=TECH8798).
This on a fresh installation of BE2012 that we installed this morning, fully updated with LiveUpdate because of multiple other issues that have started occurring over the last day or two on the previous installation. These credentials were working until yesterday the backups started reporting that they could no longer do Incremental/Differential as the VM did not supposedly support it and the jobs were defaulting to full backups (but it had been working with success for about a week). In addition, we we're having the same issue as described in this post (http://www.symantec.com/connect/forums/grt-file-recovery), all servers were pushed the RAWS agent and were publishing their FQDN to BE but GRT restores were unavailable until we removed and re-added the server manually using the FQDN, but this only worked for 80% of the servers, the remainder could still not get GRT restores going. Also, one of our DC could not backup the AD with or without GRT despite removing and re-installing the RAWS agent multiple times, removing and re-adding the server to BE using FQDN, NetBIOS, etc...
I can hosnestly say that this is the worst BE version I have ever worked with, and I have been working with Backup Exec since version 10.