Still a valid suggestion of something to look at..
Output of the following commands reveal anything ?
iptables -L - I guess this should be ACCEPT for all policies since you intimated that you don't have local firewall running on the box..
netstat -lanp | grep :22 - Is the SSH Daemon actually listening on all IP's and the correct port
another place to look if all of that is correct, is in the sshd_config
is sshd configured to use tcp wrappers ? if so is hosts.allow and hosts.deny configured correctly ?