Try logging on with "ssh -vv <user@remote-host>". That will post more debug information. Post the results.
Check the connection with the telnet client. For example:
Code:
telnet qosmio 22
Trying 192.168.1.100...
Connected to qosmio.
Escape character is '^]'.
SSH-2.0-OpenSSH_5.4
Protocol mismatch.
Connection closed by foreign host.
This test will indicate whether the ssh port is open on the remote server.