I have a group of Ubuntu 14.04 workstations that are all clones deployed via image. After imaging, they are assigned a static IP and they also delete/regenerate their host keys. Each of them on their own seems fine, they can connect to the file server, computing cluster, etc. just fine, but they can't connect to each other via SSH, and just hang endlessly (until they time out after ~10 minutes) on
debug1: SSH2_MSG_KEXINIT sent.
I can connect to them all just fine via a Windows laptop, or an older 12.04 workstation, or a 12.04 server, or from one problem workstation to another by hopping through anything else, but not like-to-like.