Amazon EC2 RSA key stopped authenticating - Permission denied (publickey)

Question

Authenticating to our Ubuntu EC2 instance worked fine until a little while ago. All of a sudden, the key is being rejected. When we create a new instance with the keypair, we're able to connect to the instance perfectly, so it appears to be an issue with the existing instance. Port 22 is open.

Any suggestions on what to look at from a configuration standpoint so we can fix this? Any thoughts on how we can get into the box?

Here is the SSH debug output. Is there anything obviously amiss?

Thanks so much!

$ ssh -v -i ~/zzz.pem ubuntu@###.###.###.###
OpenSSH_5.2p1, OpenSSL 0.9.8l 5 Nov 2009
debug1: Reading configuration data /etc/ssh_config
debug1: Connecting to ###.###.###.### [###.###.###.###] port 22.
debug1: Connection established.
debug1: identity file zzz.pem 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 '###.###.###.###' is known and matches the RSA host key.
debug1: Found key in /zzz/.ssh/known_hosts:18
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: Offering public key: /zzz/.ssh/id_rsa
debug1: Authentications that can continue: publickey
debug1: Offering public key: zzz.txt
debug1: Authentications that can continue: publickey
debug1: Trying private key: zzz.pem
debug1: read PEM private key done: type RSA
debug1: Authentications that can continue: publickey
debug1: No more authentication methods to try.
Permission denied (publickey).

Answer 1

We figured out what was wrong here. A user on the box overwrote the main ~/.ssh/authorized_keys - he was able to log in and check that file and add the master .pem key back in.