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.