I created a new Amazon Linux AMI instance and could connect just fine via ssh. Then I assigned an elastic IP to the instance and ssh suddenly stopped working.
Debug output:
debug1: Trying private key: theduke.pem
debug1: read PEM private key done: type RSA
debug3: sign_and_send_pubkey
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey
debug2: we did not send a packet, disable method
debug1: No more authentication methods to try.
Permission denied (publickey).