If you have root access to the server, the easy way to solve such problems is to run sshd in debug mode, by issuing something like /usr/sbin/sshd -d -p 2222 on the server (full path to sshd executable required, which sshd can help) and then connecting from the client with ssh -p 2222 user@host