May want to use DNSDIAG to check and verify that all your DNS is working properly and systems are finding all the right Servers. Check and verify that REPLICATION is working correctly.

Sound more like a Network issue then a KiX issue.