Ssh – Intermittent ‘ssh_exchange_identification: Connection closed by remote host’ error

While there are many questions on this site and others addressing this very issue, I haven't yet found one that seems to address what I'm experiencing.

When trying to ssh a linux box from a MBpro running Lion, I get the following error:

gjohnson5@Gentrys-MacBook-Pro:~$ ssh -v user@server_name
OpenSSH_5.6p1, OpenSSL 0.9.8y 5 Feb 2013
debug1: Reading configuration data /etc/ssh_config
debug1: Applying options for *
debug1: Connecting to server_name[ip_address] port 22.
debug1: Connection established.
debug1: identity file /Users/gjohnson5/.ssh/id_rsa type -1
debug1: identity file /Users/gjohnson5/.ssh/id_rsa-cert type -1
debug1: identity file /Users/gjohnson5/.ssh/id_dsa type -1
debug1: identity file /Users/gjohnson5/.ssh/id_dsa-cert type -1
ssh_exchange_identification: Connection closed by remote host

The strange thing is that I get this error intermittently. Sometimes rebooting my machine and trying again will get me into the server no problem. Other times, the error persists. Occasionally, I will successfully log on, close the connection, try to reconnect a few seconds later, and then receive the error.

Now, I've tried clearing the ~/.ssh/known_hosts file, and I've found that trying to log on as a different user on my same machine still throws the error. I cannot check /etc/hosts.allow and /etc/hosts.deny since I cannot access the server and my employer's IT is, unfortunately, being unresponsive. I can't imagine that would be the issue, however, as I am occasionally able to log into the server using my machine. It seems like the problem might be with some configuration on my machine (??), though I'm relatively inexperienced with this and wouldn't know where to start looking.

EDIT:
As per request, this is the result of checking MaxStartups:

grep MaxStartups /etc/ssh/sshd_config
#MaxStartups 10:30:60