I had a similar problem...
Check your logs /var/log/secure and messages, this will at least let you know if the attempted connections arrived or not. If so you will probably see a similar message to what you received through your client. If your machine is rejecting these sessions make the adjustments to your /etc/hosts.allow and hosts.deny files. You will probably need something a little more secure but:

sshd sshd1 sshd2 : ALL : ALLOW

Should work to test at least...