This has happened to me multiple times. I have used Amazon Linux AMI 2013.09.2 and Ubuntu Server 12.04.3 LTS which are both on the free tier.
Every time I have launched an instance I have permission denied show up. I haven't verified this but my theory is that the server is not completely set up before I try to ssh into it. After a few tries with permission denied, I wait a few minutes and then I am able to connect. If you are having this problem I suggest waiting five minutes and trying again.