I have two Ubuntu machines on the same network. I installed openssh-server and client. When I try to connect through the terminal I get the following message: "Permission denied, please try again" . Then after attempting to type my password in get the last message: " Permission denied (publickey,password)" However I can ssh to the computer through Nautilus, with no problem.
Logging in from the terminal by default tries to log into the remote machine with your username on the local machine. In Nautilus you have to explicitly type in your username on the remote machine. I am guessing that your local and remote usernames do not match.