So if you get this message
Too many authentication failures for ubuntu,
It's usually because you have tried too many private_keys to authenticate against the user ubuntu
in your server.
You can get more info here:
https://superuser.com/questions/187779/too-many-authentication-failures-for-username
Try running this:
ssh-add -l
ssh-add -D
You may have too many keys stored in your local ssh-agent.
If you get this:
Permission Denied (Public key).
it generally means that your public key is not in the ~ubuntu/.ssh/authorized_keys file on the server. You can actually debug by creating a snapshot of your EBS volume (if you are using EBS). Then create a new volume from the snapshot and then attach the volume to another running EC2 instance.
http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/ebs-attaching-volume.html
That way you can see what's in your /home/ubuntu/.ssh/ directory
ssh-add <private_key>
first.