Amazon EC2 – No SSH After Reboot, Connection Refused

I've replicated this two or three times, so I'm guessing there's something wrong with what I'm doing.

Here are my steps:

1. Launch new instance via EC2 Management console using: Ubuntu Server 13.10 – ami-ace67f9c (64-bit)
2. Launch with defaults (using my existing key pair)
3. The instance starts. I can SSH to it using Putty or the Mac terminal. Success!
4. I reboot the instance

5. 10 minutes later, when the instance should be back up and running, my terminal connection shows:

   stead:~ stead$ ssh -v -i Dropbox/SteadCloud3.pem ubuntu@54.201.200.208
   OpenSSH_5.6p1, Op`enSSL 0.9.8y 5 Feb 2013
   debug1: Reading configuration data /etc/ssh_config
   debug1: Applying options for *
   debug1: Connecting to 54.201.200.208 [54.201.200.208] port 22.
   debug1: connect to address 54.201.200.208 port 22: Connection refused
   ssh: connect to host 54.201.200.208 port 22: Connection refused
   stead:~ stead$
   

Fine, I understand that the public IP address can change, so checking the EC2 management console, I verify that it is the same. Weird. Just for fun, I try connecting with public DNS hostname: ec2-54-201-200-208.us-west-2.compute.amazonaws.com. No dice, same result.

Even using the Connect via Java SSH client built into the EC2 console, I get Connection Refused.

I checked the security groups. This instance is in group launch-wizard-4. Looking at the inbound configuration for this group, Port 22 is allowed in from 0.0.0.0/0, so that should be anywhere. I know that I'm hitting my instance and this is the right security group, because I can't ping the instance. If I enable ICMP for this security group, all of a sudden my pings go through.

I've found a few other posts around the internet with similar error messages, but most seem to be easily resolved by tweaking the firewall settings. I've tried a few of these, with no luck.

I'm guessing there's a simple EC2 step I'm missing. Thanks for any help you can give, and I'm happy to provide more information or test further!

Update – Here are my system logs from the Amazon EC2 console: http://pastebin.com/4M5pwGRt