I have a Solaris 10 server on another network. I can ping it and telnet to it, but ssh doesn't connect. PuTTY log contains nothing of interest (they both negotiate to ssh v2) and then I get

"Event Log: Network error: Software caused connection abort".

ssh is defintely running:

svcs -a | grep ssh
online         12:12:04 svc:/network/ssh:default

Here's an extract from the server's /var/adm/messages (anonymised)

Jun  8 19:51:05 ******* sshd[26391]: [ID 800047 auth.crit] fatal: Read from socket failed: Connection reset by peer

However, if I telnet to the box, I can login to ssh locally. I can also ssh to other (non-Solaris) machines on that network fine so I don't believe that it's a network issue (though, since I'm a few hundred miles away, I can't be sure).

The server's firewall is disabled, so that shouldn't be a problem

root@******** # svcs -a | grep -i ipf
disabled       Apr_27   svc:/network/ipfilter:default

Any ideas what I should start checking?

Update: Based on the feedback below, I've run sshd in debug mode. Here's the client output:

$ ssh -vvv root@machine -p 32222
OpenSSH_5.0p1, OpenSSL 0.9.8h 28 May 2008
debug2: ssh_connect: needpriv 0
debug1: Connecting to machine [X.X.X.X] port 32222.
debug1: Connection established.
debug1: identity file /home/lawrencj/.ssh/identity type -1
debug1: identity file /home/lawrencj/.ssh/id_rsa type -1
debug1: identity file /home/lawrencj/.ssh/id_dsa type -1
debug1: Remote protocol version 2.0, remote software version Sun_SSH_1.1
debug1: no match: Sun_SSH_1.1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.0
debug2: fd 3 setting O_NONBLOCK
debug1: SSH2_MSG_KEXINIT sent
Read from socket failed: Connection reset by peer

And here's the server output:

root@machine # /usr/lib/ssh/sshd -d -p 32222
debug1: sshd version Sun_SSH_1.1
debug1: read PEM private key done: type RSA
debug1: private host key: #0 type 1 RSA
debug1: read PEM private key done: type DSA
debug1: private host key: #1 type 2 DSA
debug1: Bind to port 32222 on ::.
Server listening on :: port 32222.
debug1: Bind to port 32222 on 0.0.0.0.
Server listening on 0.0.0.0 port 32222.
debug1: Server will not fork when running in debugging mode.
Connection from 1.2.3.4 port 2652
debug1: Client protocol version 2.0; client software version OpenSSH_5.0
debug1: match: OpenSSH_5.0 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-Sun_SSH_1.1
debug1: list_hostkey_types: ssh-rsa,ssh-dss
debug1: Failed to acquire GSS-API credentials for any mechanisms (No credentials were supplied, or the credentials were unavailable or inaccessible
Unknown code 0
)
debug1: SSH2_MSG_KEXINIT sent
Read from socket failed: Connection reset by peer
debug1: Calling cleanup 0x4584c(0x0)

This line seems a likely candidate:

debug1: Failed to acquire GSS-API credentials for any mechanisms (No credentials were supplied, or the credentials were unavailable or inaccessible