First:
After you've created your putty key under Windows (puttykey.ppk), copy it to your Ubuntu server. We'll assume you have it in your home directory on your Ubuntu server which is ~/.
So, that file is now ~/puttykey.ppk
On your Ubuntu box, run a terminal (or SSH in from your Windows box) and:
sudo apt-get install putty
When that's done, you now have putty on Ubuntu. Next do:
puttygen ~/puttykey.ppk -L > ~/.ssh/id_rsa.pub
If you're not familiar with Unix/Linux then you won't realize this, but the key output is being redirected to a file named "id_rsa.pub" in the .ssh directory in your home directory on the Ubuntu server.
Finally, create the private key on Ubuntu using:
puttygen ~/puttykey.ppk -O private-openssh -o ~/.ssh/id_rsa
Now you should be able to do public key logins to Ubuntu. You MAY still have an issue due to permissions, so I'd recommend also doing:
address
chmod 700 .ssh
chmod 600 .ssh/id_rsa*
Good luck.
I'm pretty sure that is completely wrong since the id_rsa* files .ssh are the public/private key files of THAT machine, and do not specify which public key is allowed to connect. They would only be used if you ssh'd from that machine to somewhere else. Furthermore there should be no need to create ANY keys whatsoever on the host machine.
Rather, you want to append your public key you created with putty on your client machine to the authorized_keys file in the ~/.ssh directory on the host machine. If that file does not exist create it and then run "chmod 600 authorized_keys". Depending on the format putty uses you might have to convert it to the openssh format first. There should be one key per line in the authorized_keys file, e.g. it should look similar to this:
So basically: append the .pub file you created on the client machine to the authorized_keys file of the host machine