I am not able to connect to my m1.small instance after rebooting it.

I have already associated the public IP with this instance. Upon checking the system log, this seems to be the issue:

cloud-init-nonethttp://11.84: waiting 10 seconds for network device
cloud-init-nonethttp://21.85: waiting 120 seconds for network device
cloud-init-nonethttp://141.85: gave up waiting for a network device.
Cloud-init v. 0.7.3 running 'init' at Sun, 18 May 2014 07:02:55 +0000. Up 142.54 seconds.
ci-info: +++++++++++++++++++++++Net device info++++++++++++++++++++++++
ci-info: +--------+-------+-----------+-----------+-------------------+
ci-info: | Device | Up | Address | Mask | Hw-Address |
ci-info: +--------+-------+-----------+-----------+-------------------+
ci-info: | lo | True | 127.0.0.1 | 255.0.0.0 | . |
ci-info: | eth0 | False | . | . | 02:43:xx:xx:xx:xx |
ci-info: +--------+-------+-----------+-----------+-------------------+
ci-info: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!Route info failed!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

A bunch of these follow the above message:

2014-05-18 07:02:56,178 - url_helper.pyWARNING: Calling http://169.254.169.254/2009-04-04/meta-data/instance-id failed 0/120s: request error [HTTPConnectionPool(host='169.254.169.254', port=80): Max retries exceeded with url: /2009-04-04/meta-data/instance-id (Caused by : Errno 101] Network is unreachable)

This is obviously related to the network interface not being working correctly. I have tried this so far:

1. Relaunch a new instance from the custom AMI (created from EBS) of the failing instance. The same error shows up in the logs.

2. Attach a new network interface to the EC2 instance. The error still persists. eth1 shows up in the list but the "up" column is False.