very rarely (3 times in beta testing of 100+ instances), I've seen inability to connect to an ec2 instance. ssh client gives:
ssh_exchange_identification: Connection closed by remote host
In 2 of 3 cases, there were no keys written to the ssh console, but that is likely due to bug 606373. All of the 3 cases were on amd64 systems (where I've ran into race conditions more often).
Googling for this gives lots of results, mostly related to networking or configuration issues, but that is not the case here, as the systems are identically configured to dozens of other instances that work correctly.
One thing that stuck out to me was http://www.linuxquestions.org/questions/linux-software-2/ssh_exchange_identification-connection-closed-by-remote-host-103423/ . Which seemed to be a possibility for a upstart race condition (if a tmp dir wasn't available yet.).
ProblemType: Bug
DistroRelease: Ubuntu 10.10
Package: openssh-server 1:5.5p1-4ubuntu3
ProcVersionSignature: User Name 2.6.35-19.28-virtual 2.6.35.3
Uname: Linux 2.6.35-19-virtual x86_64
Architecture: amd64
Date: Thu Sep 2 01:59:37 2010
Ec2AMI: ami-48b3993c
Ec2AMIManifest: ubuntu-images-testing-eu/ubuntu-maverick-daily-amd64-server-20100831.manifest.xml
Ec2AvailabilityZone: eu-west-1a
Ec2InstanceType: m1.large
Ec2Kernel: aki-4feec43b
Ec2Ramdisk: unavailable
ProcEnviron:
PATH=(custom, user)
LANG=en_GB.UTF-8
SHELL=/bin/bash
SourcePackage: openssh
Attaching a console log without console keys.