I then did: service sshd restart
<snip>
Have you restarted the ssh daemon after changing the config file?
Ooops, I really need to not post to the mailing list when I am tired.
My second question still stands, Also, have you run nmap on your host to verify that the port is open?
Also, have you restarted the iptables service after changing the firewall rules?