Does the security group (firewall configuration) allow SSH access?
I had this problem, and this thread almost helped. Once I fixed it, I wanted to fill in this almost-perfect answer.
More specifically - on the AWS management console page, select Security Groups in the left panel (towards the bottom)
On the bottom-right panel, select "Inbound" tab, and make sure "Custom TCP rule" is selected.
Enter 22 for the port number, click the "Add rule" button, then the "apply rule changes" button.
No need to restart or reboot your instance, just need to enable TCP port 22 inbound
telnet public_DNS_from_amazon 22? This would rule out the firewall. – Andrew M. Jan 28 '11 at 2:07nmap -PN public_DNS_from_amazon -p 22. (-PNin case the firewall blocks ping requests) – Lekensteyn Feb 12 '11 at 11:00