"Server abandoned our key" issue while connecting to Amazon Linux EC2 AWS Image by Putty

I know this question has been asked and answered before, but I can't seem to get it to work, although I have checked all the steps three times in both the Amazon doc and StackOverflow.

So here we are: yesterday I launched an Amazon EC2 instance with an Amazon Linux image - the one provided by Amazon itself. I created a key pair for my Mac and it is 100% good - it works.

But today, trying to connect from work, from my PC, I cannot make this work for Putty.

Steps I took:

• Created a new key pair
• Used by PuttyGen to convert .pem file to .ppk
• Created a new session on Putty, making sure the host is ec2-user@ec2-54-XXX-YYY-ZZZ.us-west-1.compute.amazonaws.com (I won't paste my full ec2 host explicitly)
• The private key associated with this session that I previously generated.
• Try to connect from Putty.

What I get:

This message: Using username "ec2-user". The server refused our key

And a pop-up titled "Fatal Error Loss" that says "Disabled: No Authentication Methods Available"

Please help, I tried everything:

• Changing user to root and ubuntu
• creating your own public / private key using PuttyGen
• setting the IP address of the DNS name

Nothing works ... And the worst thing is that yesterday from my Mac, with a different pair of keys and using vSSH, it worked.

I do not understand.

Thanks in advance for your precious help.

Nicolas.