authentication problem? ssh, ftp borked 10.3.9

I set up my server on a private IP and then migrated it to its final co-location with a public IP. I lost some services along the way though, and I can't, for the life of me, figure out why. I used the changeip command and most services are working (ARD, mail, web)

The main one is ssh, since I can't get into my server at the command line. ssh -vvv admin@host spits out the following and hangs at SSH2_MSG_KEXINIT:

OpenSSH_3.6.1p1+CAN-2004-0175, SSH protocols 1.5/2.0, OpenSSL 0x0090702f
debug1: Reading configuration data /etc/ssh_config
debug1: Rhosts Authentication disabled, originating port will not be trusted.
debug2: ssh_connect: needpriv 0
debug1: Connecting to mail.example.com port 22.
debug1: Connection established.
debug1: identity file /Users/gabe/.ssh/identity type -1
debug1: identity file /Users/gabe/.ssh/id_rsa type -1
debug1: identity file /Users/gabe/.ssh/id_dsa type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_3.6.1p1+CAN-2004-0175
debug1: match: OpenSSH_3.6.1p1+CAN-2004-0175 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_3.6.1p1+CAN-2004-0175
debug3: Trying to reverse map address 217.139.74.156.
debug1: Miscellaneous failure
No credentials cache found

debug1: Miscellaneous failure
No credentials cache found

debug1: SSH2_MSG_KEXINIT sent
Connection closed by --IP ADDRESS REMOVED--
debug1: Calling cleanup 0x1c540(0x0)

system.log on the server says,

SSH2_MSG_KEXINIT

At first I thought it was a DNS reverse-mapping or an ssh_host_key problem, but I got the reverse DNS taken care of and rebuilt all my ssh keys. The reason I think it's some kind of Open Directory or authentication problem is because I enabled ftp and it hangs prior to auth too.

Anybody recognize this problem and have any ideas? I'm sort of dead in the water and need to get this server working right ASAP.

Thanks!