ssh: 12.04 Cannot open authorized keys

I cannot get sshd to read authorized_keys (see auth.log dump for more) and thus it won't allow RSA-based connections. I'm stuck with password log-in (and trying to transition away from that). It claims that the authorized_keys file does not exist. It does (exist) and is accessible by <user> (600). sshd has NOT been added to <group> (it's a standard Ubuntu Server 12.04 install).

Changes to the dumps, etc. (below):
OpenSSH user: <user> (user name is of the form "abcd-efgh", btw)
OpenSSH user's group: <group> (i.e., same name as user, standard Ubuntu install)
OpenSSH client ip: <client ip>
OpenSSH server hostname: <host>

System Info:
This is a new Ubuntu Server (12.04) install. All patches have been applied (as of the timestamps you see below). This is a "textbook" installation and I can log in with password fine (and then sudo). root is as configured by Ubuntu installer (not using it directly). The machine ONLY has OpenSSH installed (i.e., choose OpenSSH in Ubuntu Installation and nothing else). OpenSSH on the machine is accessible via direct and network interfaces (but RSA-based auth fails always). Not using DSA. Not allowing OpenSSH v1.

It shouldn't matter, but... I'm connecting (via TCP) from a Windows 7 client via PuTTY (with Pageant configured to present the private key, etc.). The private key (.ppk form) is a "textbook" password protected, RSA-2, 1024b key.

Files Info:
/home/<user> is 750
/home/<user>/.ssh is 700 (was 750)
/home/<user>/.ssh/authorized_keys is 600 (was 640)
ALL of those directories/files are owned by <user> and <group> (i.e., standard Ubuntu Server installation stuff)

authorized_keys HAS a single, valid ssh-rsa key line plus one \n (atend). There are no extra chars at the start of the file (i.e., first char is 's' of ssh-rsa)

There are NO other files in ~/.ssh/

Dump of (relevant part of) auth.log
----------
May 19 12:22:06 <host> sshd[7558]: debug1: userauth-request for user <user> service ssh-connection method none [prea
uth]
May 19 12:22:06 <host> sshd[7558]: debug1: attempt 0 failures 0 [preauth]
May 19 12:22:27 <host> sshd[7558]: debug1: PAM: initializing for "<user>"
May 19 12:22:27 <host> sshd[7558]: debug1: PAM: setting PAM_RHOST to "<client ip>"
May 19 12:22:27 <host> sshd[7558]: debug1: PAM: setting PAM_TTY to "ssh"
May 19 12:22:27 <host> sshd[7558]: debug1: userauth-request for user <user> service ssh-connection method publickey
[preauth]
May 19 12:22:27 <host> sshd[7558]: debug1: attempt 1 failures 0 [preauth]
May 19 12:22:27 <host> sshd[7558]: debug1: test whether pkalg/pkblob are acceptable [preauth]
May 19 12:22:27 <host> sshd[7558]: debug1: Checking blacklist file /usr/share/ssh/blacklist.RSA-1024
May 19 12:22:27 <host> sshd[7558]: debug1: Checking blacklist file /etc/ssh/blacklist.RSA-1024
May 19 12:22:27 <host> sshd[7558]: debug1: temporarily_use_uid: 1000/1000 (e=0/0)
May 19 12:22:27 <host> sshd[7558]: debug1: trying public key file /home/<user>/.ssh/authorized_keys
May 19 12:22:27 <host> sshd[7558]: debug1: Could not open authorized keys '/home/<user>/.ssh/authorized_keys': No su
ch file or directory
May 19 12:22:27 <host> sshd[7558]: debug1: restore_uid: 0/0
May 19 12:22:27 <host> sshd[7558]: Failed publickey for <user> from <client ip> port 55099 ssh2

Dump of 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 VERBOSE

# Authentication:
LoginGraceTime 120
PermitRootLogin no
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 no
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

# Restrict access to the following user(s).
#AllowUsers <user>