Didn't find any web search hits, so I thought I'd document it:
$ ssh -v
...
debug1: Trying RSA authentication via agent with ''
debug1: Received RSA challenge from server.
debug1: Sending response to RSA challenge.
debug1: Remote: RSA authentication accepted.
Received disconnect from : Access denied.
I had installed linux on a new machine, and then copied over a bunch of stuff to attempt to mimic an existing machine. I copied over /home (including the ~/.ssh/authorized_keys authenticated against here), /etc/passwd, and /etc/group. The problem was that I had not copied over /etc/shadow.
Feeling a little more arcane than usual.