Process for telling when a new ec2 host can be connected to

Question

I've been using fabric and boto to start up new ec2 hosts for some temporary processing but I've always had trouble knowing when I can connect to the host. The problem is that I can ask ec2 when something is ready but it's never really ready.

This is the process that I've noticed works best (though it still sucks):

1. Poll ec2 until it says that the host it "active"
2. Poll ec2 until it has a public_dns_name
3. Try to connect to the new host in a loop until it accepts the connection

But sometimes it accepts the connection seemingly before it knows about the ssh key pair that I've associated it with and then asks for a password.

Is there a better way to decide when I can start connecting to my ec2 hosts after they've started up? Has anyone written a library that does this nicely and efficiently?