Did you remember to ensure that your IP address (or netblock) is
allowed to send traffic to TCP port 22 in your security group for
the instance that you just deployed? You can check this by going
running the 'ec2-describe-group' command from the EC2 Toolkit, or
by using Amazon's Console and heading to EC2 -> Security Groups
and viewing the security group assigned to that instance.