I spent about 3 hours trying to figure out how to connect to a linux box from my windows machine using putty without having to send the password.

This is connecting to an Ubuntu server that is using OpenSSH. The private key is SSH-2 RSA, 1024 bits. I am connecting using SSH2.

I have run into the more common problems already:

1. Putty generated the public key in the "wrong format". I have corrected this (as seen on this blog post). However, since I am not yet connected, I cannot absolutely confirm that this file is in the correct format. The key is all on a single line now, and I have tried adding/removing line breaks at the end of the file. I've also tried the public file doctoring process a few times to ensure that I haven't flubbed up the manual conversion. Even so, I have no way to verify accuracy here.
2. The permissions were at once point wrong as well, specifically meaning that the file had too many permissions. I had to solve this too and I know it got past this because I no longer see a related error in /var/log/auth.log.
3. I've tried both authorized_keys and authorized_keys2 in case the server has an old version of OpenSSH, but this changed nothing.
4. I do have access as a user. After this keyfile stuff fails, I can enter my password instead

The only remaining nibble of information I have is that it claims I have the alleged password wrong:

sshd[22288]: Failed password for zzzzzzz from zz.zz.zz.zz port 53620 ssh2

Even so, as far as I can tell, this is just a lazy try/catch somewhere, since I don't think there's a password involved at all.

I see nothing else in any of the /var/log files of use. What else could be wrong?