Just now I got this error when trying to enable HA on a cluster with two ESXi4 hosts:

"Cannot complete the configuration of the HA agent on the host. Other HA configuration error."

When experiencing HA configuration issues there are a couple of steps I usually take to try to fix the experienced issues:

• Click “reconfigure for VMware HA” and see if the issue is still there, if so:
  • Is DNS configured and does it actually work? If not, fix and reconfigure for HA.
  • Is the gateway reachable? If not, fix and reconfigure for HA.

This usually solves 75% of the issues. If it hasn’t been fixed the next step I usually take is unloading the agent and restarting the management services. Although it is pretty rigurous it is the fastest way of fixing HA issues.  In my case I am using ESXi and this is what I needed to do to clean up the host:

• Disable HA on the cluster
• /opt/vmware/aam/VMware-aam-ha-uninstall.sh
• /sbin/services.sh restart
• Enable HA on the cluster

This solved the issue I had with HA,