Only on one connection server? The agents will connect to a single server, but messages are meant to be routed between them - so if you're seeing "unreachable" on one server but not the other you're likely looking at messaging issues between the connection servers themselves. Have you looked at the connection server logs to see if there are other related errors/timeouts? Can you confirm that traffic on port 4100 (JMS inter-router communication) is healthy?
The two connections servers are on the same network with not firewall etc between them so I assume the 4100 traffic is allowed. I will confess to being unsure about what to look for in the connection server logs but no obvious time out errors. Any clues?
It could be ADAM replication issue between the Connection Servers. Can you please check the status of the connection servers on the dashboard.
did you tried to restart the connection servers to clear the ADLDS Synchronization between servers?