I've seen this a few times:
1) Put in Maintenance mode
2) Move out of cluster (removes HA client)
3) Reboot (not sure if needed, but why not)
4) Move back into cluster.
That's assuming you've chased down any other possibilities of routing, dns, firewalls (shouldn't be any) cables, etc.
There are also KBs on how to manually uninstall and re-install the HA agent.... hope you don't have to go there!
