AWS EC2 keep refusing my private SSH 2 key

Question

Already looked for a solution but nothing seems to be helpfull, I'm doing everything that is meant to be made and my instance keeps returning me the message "Server refused our key".

Here's what I've been doing:

1) Create Instance;
2) Download the .pem key;
3) PuttyGen to transform it in a private .ppk (SSH-2 RSA);
4) Associate an Elastic IP to the Instance;
5) Connect through 22 with the correct auth key generated on the 3rd step;
6) Server asks for username, insert "ubuntu" (using 12.04.1 LTS);
7) Server returns "Server refused our key".

Tried to reboot a hundred times, tried SSH-1 RSA, tried public key instead of private key, tried keys with passphrase, tried everything.

Someone else is experiencing this?

Edit:

Thought it might be a security problem, here are my rules if that helps:

http://i.stack.imgur.com/Y3I2s.png

Answer 1

Just got into the same issue. AWS instance recognize only the key which was specified during the instance creation. All later changes to the key list will not affect already created instance.

Edit: actually, here problem was in incorrect export to .ppk file using Puttygen. See comments below.