Having the same issue here.  We've got a number of v5 hosts on build 474610 without an issue.  Had the problem going from v5 474610 -> 515841 and v4.1 433742 -> v5 515841.  "vCenter requires verified host SSL certificates" box already checked, tried unchecking and manually verify...still a no go.  I have a case open with VMware and will post an update when we narrow down the problem.

With "vCenter requires verified host SSL certificates" unchecked I add the host, it shows up in the box within the SSL Settings section, and check the "Verified" checkbox.  With the "vCenter requires verified host SSL certificates" checked I'm immediately prompted upon adding a host to vCenter on whether I want to trust the host or not.  If I click yes the process of adding the host continues.  If I click no I'm denied adding the host.  The one odd thing, though, is once the host is verified it disappears from the box in the SSL Settings section...I expected all hosts to be listed with their SHA1 thumbprint information and whether verified or not.

I have a small update...patched our test environment hosts running on a completely separate instance of vCenter and they came back with no HA errors.  So for some reason our production vCenter doesn't play well with build 515841.  And the troubleshooting continues...

With the help of Elisha (eziskind) it looks like we got it nailed down.  The HA agent had to be manually uninstalled then automatically re-pushed to the host from vCenter.  Really strange that the issue happened only after the 12/15 patches, but at least I know what to do now.  What we did:

- place host into Maintenance Mode

- take a copy of /opt/vmware/uninstallers/VMware-fdm-uninstall.sh (we copied to /tmp)

- from the location you made a copy of the file, run the command (./VMware-fdm-uninstall.sh)

- you should see a short pause before it gets back to the prompt (you'll see why I mention this below)

- exit host out of Mainenance Mode and within the "Recent Tasks" area you should see the client being pulled from vCenter and installing

With one host this went without a hitch.  On the second host, though, when running the installer it immediately went back to the prompt, not a short delay like with the first.  Took it out of the cluster & vCenter, re-added, still didn't work.  Rebooted the host, made another copy of the uninstaller, and it removed successfully.