I tried logging in as a regular user also. Still no luck. I usually never log in as root altogether but when I went onto the machine to try fixing the ssh problem I logged in as root for some reason.
The other problem I've found is that when I tried re-installing ssh there were a lot of packages that had errors/needed upgrading (2 of which were openssh-server and openssh-client), so I did a dist-upgrade, and there were problems processing 2 packages:
openssh-server and ssh
Here is a summary of the error I got when doing a dist-upgrade:
Setting up openssh-server (4.3p2-8)...
/var/run/sshd must be owned by root and not group or world-writable.
invoke-rc.d: initscript ssh, action "restart" failed.
dpkg: error processing openssh-server (--configure):
subprocess post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of ssh:
ssh depends on openssh-server; however:
Package openssh-server is not configured yet.
dpkg: error processing ssh (--configure):
dependency problems - leaving unconfigured
Errors were encountered while processing:
And to answer anomie's question, I haven't added anything to /etc/hosts.allow or /etc/hosts.deny unless something was added automatically. As for the sshd_config, whatever the default is, that's what I've been using. I haven't made any changes to ssh myself.