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:
chmod 700 .ssh
chmod 600 .ssh/id_rsa*
Good luck.