Hmmm...  So were you trying to SSH to the external IP?  If so, what does your
sshd2_config or sshd_config file have for the IP it is to bind to (if any). 
What default permissions did it come with for who could log in.  I'm used to ssh
from www.ssh.com that comes with it wide open, including letting root login
remotely (not good :(  ).

Also if it was SSH I'm used to it bouncing me back to the password prompt over
and over when I'm not allowed in.  That's its way of hiding what is wrong with
the connection (whether it's a bad password or your IP isn't allowed to
connect).  Again this is with SSHd running standalone.

Since /etc/hosts.{deny,allow} are both empty that might not be causing a
problem, but wouldn't discount inetd as the troublemaker.

> > That has the signature of an exploited machine.  I have seen several of
> > these with the same issues.  When people exploit the CRC-32 ssh hole,
> > the rootkits disable ssh to keep others from using the same exploit,
> > and it has the affect of locking legit users out as well.  I'm not
> > saying it's guaranteed to be it, but it is possible.  If you used any
> > redhat distribution or several others they come default with an old
> > (pre v2.9) OpenSSH which is vulnerable.
> >
> > Lowell
> 
> I built this machine from the ground up from source copies of the latest
> distributions of each package. I'm running OpenSSH_3.0p1, with protocols
> 1.5/2.0. The system was just recently installed to the outside world a few
> seconds ago, so it's not possible for it to be rooted this early. =op