I had a similar problem connecting to recently launched AWS EC2 instances. Apparently, instances may not yet be available via ssh, even if their status is already running.
There seems to be no right solution, this is the most elegant I got:
while True:
try:
run('whoami')
break
except Exception, e:
print "instance not yet reachable, wait a little bit", e
time.sleep(10)