fatal: mm_request_receive_expect error

We have a client that is coming through our PIX firewall (rules are set properly) and trying to SSH into our Linux box. We are using SLED 10 with openssh-4.2p1-18.25. He previously was able to SSH in until will rebuilt the server (hardware failure). Now when he tries login I get this error in /var/log/messages:

Oct 16 16:22:12 dss-cs99la07 sshd[16641]: fatal: mm_request_receive_expect: read: rtype 48 != type 46

..He is using a Windows SSH client. My first guess was he still had our old certificate but it prompts him to accept the new one and he does.

I have confirmed myself and others can SSH from outside the firewall so I'm pretty sure it's not a firewall issue.

Any ideas?