I was getting this error when trying to SSH to a brand new CentOS 7 VM I was setting up. I hadn't even done anything yet, so I was confused until I realized I had hit the 'MaxAuthTries' limit configred in /etc/ssh/sshd_config on the VM by issuing a single command.
I have a few (ok, 9) SSH keys in my ~/.ssh directory. When you issue an SSH connection request without specifying which key to use via the -i option, SSH tries to use each key.
The default MaxAuthTries value on a CentOS 7 box is 6.
9 > 6 = Too many authentication failures for me.
I used the console to edit /etc/ssh/sshd_config and set MaxAuthTries 30. That allowed me to put my SSH key on the VM, and now I can connect. Obviously set MaxAuthTries back to 6 when you're done.
To reset the thing that locked you out, do this (on RHEL-flavored things, anyway)
pam_tally2 --reset --user <USERNAME>