Ubuntu – Trying to do ssh authentication with key files: server refused our key

I'm trying to setup ssh authentication with key files in stead of username/password. The client is a Windows box running PuTTY and the server is a Ubuntu 12.04 LTS server.

I downloaded puttygen.exe and had it generate a key pair. In /etc/ssh/sshd_config I have this line:

AuthorizedKeysFile %h/.ssh/authorized_keys

and on my client's public key file it says this:

---- BEGIN SSH2 PUBLIC KEY ----
Comment: "my@email.address.com"
ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAIEAr3Qo6T5XU06ZigGOd3eKvfBhFLhg5kWv8lz6
qJ2G9XCbexlPQGanPhh+vcPkhor6+7OmB+WSdHeNO652kTofnauTKcTCbHjsT7cJ
GNrO8WVURRh4fabknUHPmauerWQZ6TgRPGaz0aucU+2C+DUo2SKVFDir1vb+4u83
AV1pKxs=my@email.address.com
---- END SSH2 PUBLIC KEY ----

I copied the part from "ssh-rsa AAA" to "my@email.address.com" and put that in the file ~/.ssh/authorized_keys on my server (in my own homefolder). In PuTTY under Connection > SSH > Auth I entered the path to the private key it generated on my client and saved the session settings.

I restarted the ssh server with

sudo service ssh restart

Now if I load the profile in PuTTY (I verified the private key is still in Connection > SSH > Auth and that the path is correct) and run the profile, it says

Server refused our key

I tried putting the public key in a file under the directory ./ssh/authorized_keys/ but that didn't help so I used ./ssh/authorized_keys as a file, pasting the key in it. I also tried generating a private/public key pair on the server, putting the public key in ./ssh/authorized_files and loading the private one in PuTTY on my client. Rebooting the server didn't help either.

I found that the error may be solved by putting the key in a place outside the user's home folder but that's only useful if the home folder is encrypted, which this one is not.

Also tried generating a 4096 bit key, thinking perhaps 1024 was too short.

How can I get this to work? Thanks!

EDIT:

Ok, /var/log/auth.log said:

sshd: Authentication refused: bad ownership or modes for directory /home/vorkbaard/.ssh

Google tells me ~/.ssh/ should be 700 and and ~/.ssh/authorized_keys should be 600, so I did that. Now /var/log/auth.log says:

sshd: error: key_read: uudecode AAAAB3N [etc etc etc until about 3/4 of my public key]