I have had this issue, and one of two things seems to fix it. If I wait a while (honestly I don't know how long) it starts working again. Or, if I reboot the client machine, it takes care of the issue. I can still access each machine via IP, but to use the hostname requires time or a reboot.
This was frustrating at first, but now that I understand it, it's not as big of an issue, but I do use more IP's than hostnames in my scripts and config files.