After upgrading to vSphere 5.1 you experience the following error ‘the public key in specification does not match the vCenter public key. You have to reenter the password in order to proceed’ when trying to deploy new virtual machines from templates.
The administrators password used to create the virtual machine was encrypted using a different Certificate Authority to the one installed on vCenter. This means that the password is no longer trusted.
In vCenter go to Home > Customization Specification Manager
Edit Specification > 5 Administrator Password > Re Enter Credentials > Save
If your Customization Specification is domain joined you will need to enter your credentials again under 9 Workgroup or Domain
You will now be able to deploy your VM from the template in question.