SSH not working over VPN only

EDIT: the SSH public key setup is a red herring. I actually cannot SSH to any boxes over Junos Pulse VPN, even ones where I don't have my SSH keys stored for password-less login.

I have an SSH public key setup on a UNIX box I routinely SSH to at work so that I can login quickly without having to type my password. When I am connected via ethernet at the office, it works just fine. However, when I connect over VPN, regardless of whether it is wireless or ethernet from home or from work, I get this error:

mstills:~/ $ ssh -v <IP>                                                                                                    [11:00:18]
OpenSSH_5.9p1, OpenSSL 0.9.8r 8 Feb 2011
debug1: Reading configuration data /etc/ssh_config
debug1: /etc/ssh_config line 20: Applying options for *
debug1: Connecting to ------- [--------] port 22.
debug1: Connection established.
debug1: identity file /Users/mstills/.ssh/id_rsa type 1
debug1: identity file /Users/mstills/.ssh/id_rsa-cert type -1
debug1: identity file /Users/mstills/.ssh/id_dsa type -1
debug1: identity file /Users/mstills/.ssh/id_dsa-cert type -1
ssh_exchange_identification: Connection closed by remote host

There is not much information here to work with. The closest thing I could find to my problem via Google was this: https://supportforums.cisco.com/thread/2068758

But I can't figure out how to apply that solution. The client I use to connect to VPN (if relevant) is Junos Pulse. I just started using it recently, the old client I use to connect to VPN seemed to accept the SSH key no problems.

edit: this problem definitely only occurs when using the Junos Pulse VPN client. Maybe it is related to hosts file? I have no idea…