What is causing paramiko.SSHException: Invalid packet blocking?

When I attempt to connect to one of our internal servers using paramiko (inside of fabric, for what it's worth) I get this error:

Retrieving packages from server p-websvr-004
[p-websvr-004] run: /usr/sbin/pkg_info -aD|grep "Information for"
starting thread (client mode): 0x179f090L
Banner: ------------开发者_如何学C----------------------------------------------------------
Banner: Welcome to Mycompany, Inc.  Unauthorized access, is strictly prohibited
Connected (version 2.0, client OpenSSH_4.5p1)
Exception: Invalid packet blocking
Traceback (most recent call last):
  File "/Users/crose/virtualenv/mycompany/lib/python2.6/site-packages/paramiko/transport.py", line 1491, in run
    ptype, m = self.packetizer.read_message()
  File "/Users/crose/virtualenv/mycompany/lib/python2.6/site-packages/paramiko/packet.py", line 344, in read_message
    raise SSHException('Invalid packet blocking')

Every other host we have works, as far as I can tell. What's causing this to happen, and how can I fix it?

---

First obvious question, how is this host different than the rest?

By the looks of it, it could be a bug in the SSH server. Does openssh on the command line work, and is it using a different cipher?