Prevent SSH from Advertising Version Number – Security Guide

One of your login scripts (.bashrc/.cshrc/etc.) is probably outputting data to the terminal (when it shouldn't be). This is causing ssh to error when it is connecting and getting ready to copy as it starts receiving extra data it doesn't expect. Remove output that is generated in the startup scripts.

You can check if your terminal is interactive and only output text by using the following code in a bashrc. Something equivalent exists for other shells as well:

if shopt -q login_shell; then
    [any code that outputs text here]
fi

or alternatively, like this, since the special parameter - contains i when the shell is interactive:

if echo "$-" | grep i > /dev/null; then
    [any code that outputs text here]
fi

For more information see: rsync via ssh from linux to windows sbs 2003 protocol mismatch

To diagnose this, make sure that the following is the output you get when you ssh in to the host:

USER@HOSTNAME's password: 
Last login: Mon Nov  7 22:54:30 2011 from YOURIP
[USER@HOSTNAME ~]$ 

If you get any newlines or other data you know that extra output is being sent. You could rename your .bashrc/.cshrc/.profile/etc. files to something else so that they won't output extra output. Of course there is still system files that could cause this. In that case, check with your sysadmin that the system files don't output data.

The actual problem was that my user was somehow missing from `/etc/shadow.

I will let this question to stay open for sometime so that people can put more troubleshooting advice here.