The problem is due to the certificate "Issued To" field not being the fqdn of the server. The fqdn being in the subject alternative is not enough. I guess this rules out wildcard certs too.
An addition to this, all vSphere 5.1 certs need a different subject name, you need 1 certificate for each of the following services:
SSO
Inventory Service
vCenter
Update Manager
Web Client
Log Browser
This blog is pretty complete about certificate replacement:
http://derek858.blogspot.co.uk/2012/09/vmware-vcenter-51-installation-part-1.html
