I just set up pubkey authentication on my server (running ubuntu server 10.10). If I am logged in to the server locally (at the box), then I can ssh into the server fine (from another machine). If I am not, however, I can not login and just receive the error "Permission denied (publickey)".
If I run the ssh command with the verbose flag, this is the output: http://pastebin.com/3bPaTe1u
I do not have this issue if I don't use pubkey authentication and just use password-based, but pubkey is the method I would like to use.