Virus, malware, DNS ( can you do NSlookups ) and can each machine see the other by name and then IP, is it a routing isue are you on a LAN or WAN can you tracert between the servers. Is there some firewall on that should n't be?
REplication errors are usually down to something like that. Are the times in sync and the time zones correct?
