Ubuntu – Unable SSH into Ubuntu Server

I have just completed a clean install of Ubuntu Server 11.04 x86. During installation, I selected OpenSSH, LAMP, and Tomcat as installation packages. On every previous installation of Ubuntu I have done, I can then log in to the new box by SSH using the user/password created during installation. For some reason, I cannot do that with this installation. I can log in on the command line (keyboard/monitor) just fine; however, this box is going to be placed somewhere without a keyboard and monitor, so I need to get it over SSH. Any ideas?

EDIT

/etc/ssh/sshd_config

# Package generated configuration file
# See the sshd_config(5) manpage for details

# What ports, IPs and protocols we listen for
Port 22
# Use these options to restrict which interfaces/protocols sshd will bind to
#ListenAddress ::
#ListenAddress 0.0.0.0
Protocol 2
# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
#Privilege Separation is turned on for security
UsePrivilegeSeparation yes

# Lifetime and size of ephemeral version 1 server key
KeyRegenerationInterval 3600
ServerKeyBits 768

# Logging
SyslogFacility AUTH
LogLevel INFO

# Authentication:
LoginGraceTime 120
PermitRootLogin yes
StrictModes yes

RSAAuthentication yes
PubkeyAuthentication yes
#AuthorizedKeysFile %h/.ssh/authorized_keys

# Don't read the user's ~/.rhosts and ~/.shosts files
IgnoreRhosts yes
# For this to work you will also need host keys in /etc/ssh_known_hosts
RhostsRSAAuthentication no
# similar for protocol version 2
HostbasedAuthentication no
# Uncomment if you don't trust ~/.ssh/known_hosts for RhostsRSAAuthentication
#IgnoreUserKnownHosts yes

# To enable empty passwords, change to yes (NOT RECOMMENDED)
PermitEmptyPasswords no

# Change to yes to enable challenge-response passwords (beware issues with
# some PAM modules and threads)
ChallengeResponseAuthentication no

# Change to no to disable tunnelled clear text passwords
#PasswordAuthentication yes

# Kerberos options
#KerberosAuthentication no
#KerberosGetAFSToken no
#KerberosOrLocalPasswd yes
#KerberosTicketCleanup yes

# GSSAPI options
#GSSAPIAuthentication no
#GSSAPICleanupCredentials yes

X11Forwarding yes
X11DisplayOffset 10
PrintMotd no
PrintLastLog yes
TCPKeepAlive yes
#UseLogin no

#MaxStartups 10:30:60
#Banner /etc/issue.net

# Allow client to pass locale environment variables
AcceptEnv LANG LC_*

Subsystem sftp /usr/lib/openssh/sftp-server

# Set this to 'yes' to enable PAM authentication, account processing,
# and session processing. If this is enabled, PAM authentication will
# be allowed through the ChallengeResponseAuthentication and
# PasswordAuthentication.  Depending on your PAM configuration,
# PAM authentication via ChallengeResponseAuthentication may bypass
# the setting of "PermitRootLogin without-password".
# If you just want the PAM account and session checks to run without
# PAM authentication, then enable this but set PasswordAuthentication
# and ChallengeResponseAuthentication to 'no'.
UsePAM yes

/var/log/auth.log

Jul 14 09:45:00 test sshd[544]: Received signal 15; terminating.
Jul 14 09:45:00 test sshd[601]: Server listening on 0.0.0.0 port 22.
Jul 14 09:45:00 test sshd[601]: Server listening on :: port 22.
Jul 14 09:48:51 test sshd[884]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=10.10.9.100  user=nik
Jul 14 09:48:53 test sshd[884]: Failed password for nik from 10.10.9.100 port 50295 ssh2
Jul 14 09:49:06 test sshd[884]: last message repeated 2 times
Jul 14 09:49:06 test sshd[884]: PAM 2 more authentication failures; logname= uid=0 euid=0 tty=ssh ruser= rhost=10.10.9.100  user=nik
Jul 14 09:49:25 test login[829]: pam_unix(login:auth): authentication failure; logname=LOGIN uid=0 euid=0 tty=/dev/tty1 ruser= rhost=  user=nik
Jul 14 09:49:28 test login[829]: FAILED LOGIN (1) on '/dev/tty1' FOR 'nik', Authentication failure
Jul 14 09:49:36 test login[829]: pam_unix(login:session): session opened for user nik by LOGIN(uid=0)
Jul 14 09:59:00 test sudo: pam_unix(sudo:auth): authentication failure; logname=nik uid=0 euid=0 tty=/dev/tty1 ruser=nik rhost=  user=nik
Jul 14 09:59:04 test sudo:      nik : TTY=tty1 ; PWD=/var/www ; USER=root ; COMMAND=/bin/cp /etc/ssh/sshd_config ./sshd_config
Jul 14 10:06:24 test sudo:      nik : TTY=tty1 ; PWD=/var/www ; USER=root ; COMMAND=/bin/cp /var/log/auth.log ./auth.log