The issue arises when you have deployed a vCenter server from version 4.0 and by default the self-signed certificate generated by vCenter was 512bits. If you have never replaced your certificate then it will still be 512bits. If you have upgraded your vCenter to 4.1, 5.0, 5.1 or even 5.5 then, unless you have replaced the certificate along the way, it will still be the same 512bit certificate it was when you first started out.
Nothing very wrong with this setup, until MS released KB2661254 which changed the default minimum accepted key length from 512bits to 1024bits to nudge people up the security ladder a little. This resulted in vCenter certificates no longer being supported by clients and hence stopping access to vCenter web portal.
Now the correct way to deal with this is to generate a new vCenter certificate which has at least a 1024bit key (preferably 2048bits) and this will then not only allow the updated clients to function again, but will give you a warm fussy feeling that only running your environment at a higher security level can achieve. This is, however, easier said than done.
The process of replacing certificates within vCenter is not straightforward. VMware have significantly improved the process by way of the SSL Automation Tool for vCenter 5.0 and above but this is still a fairly lengthy process which is fraught with possible danger (of breaking your vCenter deployment). This needs to be planned and tested and adequate backup and recovery processes put in place before you proceed with doing this on a mature production environment.
A short term fix to get around this is to once again trust the 512bit key and proceed as you were.
The below command can be run from a command prompt on a Windows client to revert the KBs effects:
certutil -setreg chain\minRSAPubKeyBitLength 512
Obviously, doing this will also result in the client trusting ALL 512bit keys that are out there so this should only be viewed as a short term fix whilst you plan the certificate upgrades for vCenter as recommended by VMware.
Once you have resolved the certificate issues and are now sporting a shiny new 1024bit (or 2048bit) certificate, don’t forget to revert the changes above to secure your client(s) again. This can be easily done by removing the registry entry that the above command creates here: