Hi, don't have much light to shed on this but here's a few walls to bang your head on:
/etc/hosts.{allow, deny} /etc/ssh/sshd_config #especially AllowUsers if that's there only specified users can connect, and "PasswordAuthentication yes" for obvious reasons I vaguely recall having a problem like this that was related to a screwy PAM setup, pray $DIETY that's not it, there's quite a bit of weird voodoo in those files, and I don't recall how I fixed that one... Good luck, -Jon