This was an intermittent problem. The reason for this is that ssh property MaxStartups has been reached. One of the servers we have are used by remote users, and they can be very slow at authenticating.
To verify the problem, edit /etc/ssh/sshd_config
Add the line LogLevel DEBUG2
reload sshd, e.g. '/etc/init.d/sshd reload'
Check logs in /var/log/secure
If you see something like
Sep 10 20:43:13 bombay sshd: debug1: drop connection #10
It is because MaxStartups has been reached.
Once that is confirmed, edit /etc/ssh/sshd_config again
Remove the LogLevel DEBUG2, and add MaxStartups 50 (or whatever your needs are)
reload sshd again.