Putty: Getting Server refused our key Error

I created key pair using puttygen.exe (client is windows 8). On server (Ubuntu 12.04.3 LTS), I have put my public key in ~/.ssh/authorized_keys. The public key is this:

ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAQEAopfM6RHOgnuc4Aftn3t4k5UIAT3StCAbn/vg/IMbphbXadshC+79sIlRq3P4zGzMjFTP4hKnzu6ehLV5lmj/qorq3SKT+bPO5Qrac3VbIlrGvuBFDDjP82I2Hwg3HzlsFTstqk++KToapaTYZ7jENEYyPl2wnzITJnt//+4U1o6juoXTKgdNE02hHnRZyHOV/bnkZyJJCEwJv5U0eXSThQnhmXtUxGT8U0HQNFiXfqIIVllhWiCnyrhhIaKz/CIJNAd2VmzyJzQtJtTQX8aWSNVrZju6Sv2/RncTNvsACdNgjjh/FH8PQXaep00jlJ3MOdsC8vz6VSPFbh6iKy1oLQ== rsa-key-20131231

So it's correct (one line, no comments, starts with ssh-rsa, etc.)

.ssh dir permission level is 700, authorized_keys file permission is 600. Both directory and file owned by the actual user that I try to log in.

When I try connecting I'm getting 'server refused our key' and server asks for password. That's all. Nothing is logged to /var/log/auth.log when attempting to log in with the key.

I've looked everywhere and all articles and tips mention setting chmod 600 and 700 for the file/directory and formatting the key correctly. I've done all this still getting 'refused our key' error and I'm out of ideas.

OK, there was a small typo in my key. Apparently when pasting to file the first letter was cut off and it started with sh-rsa instead of ssh-rsa.

nrathathaus - your answer was very helpful, thanks a lot, this answer is credited to you :) I did like you said and set this in sshd_conf:

LogLevel DEBUG3

By looking at the logs I realized that sshd reads the key correctly but rejects it because of the incorrect identifier.

Adding a few thoughts as other answers helped, but were not exact fit.

First of all, as mentioned in accepted answer, edit

/etc/ssh/sshd_config

and set log level:

LogLevel DEBUG3

Then try to authenticate, and when it fails, look for log file:

/var/log/secure

It will have errors you are looking for.

In my case I had to change the permissions of /home/user from 0755 to 0700 as well.