I have existing instances running and I can connect to them fine. Even if I start a new instance from one of my saved ami's I can connect to it fine but any new public or community ami (I've tried 2 offical Ubuntu ami's and 1 Fedora quickstart ami) I get permission denied (publickey). The permissions are good on my key file. I've also tried creating a new keyfile. My ec2 firewall rules are good, I've also tried creating a new group. This is the error I'm getting.

ssh -v -i ec2-keypair [email protected]
OpenSSH_5.2p1, OpenSSL 0.9.7l 28 Sep 2006
debug1: Reading configuration data /Users/chris/.ssh/config
debug1: Reading configuration data /etc/ssh_config
debug1: Connecting to ec2-xxx.xxx.xxx.xxx.compute-1.amazonaws.com [xxx.xxx.xxx.xxx] port 22.
debug1: Connection established.
debug1: identity file ec2-keypair type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.1p1 Debian-6ubuntu2
debug1: match: OpenSSH_5.1p1 Debian-6ubuntu2 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.2
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'ec2-xxx.xxx.xxx.xxx.compute-1.amazonaws.com' is known and matches the RSA host key.
debug1: Found key in /Users/chris/.ssh/known_hosts:13
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Trying private key: ec2-keypair
debug1: read PEM private key done: type RSA
debug1: Authentications that can continue: publickey
debug1: No more authentication methods to try.
Permission denied (publickey).