If you ever run into "too many authentication attempts" on sshing to a host, you'll want to add "IdentitiesOnly yes" in your ssh config. GNOME (Ubuntu et. al) helpfully throw all of your keys under .ssh into ssh-agent on login. It will then try each and every one of them in-turn until the remote site tells you to go fly a kite.

I was having trouble with every new machine giving me the "too many authentication attempts" message even before I could try a password. My .ssh/config file is littered with "PreferredAuthentication password" entries for machines that I only want to use a password. With "IdentitiesOnly yes" it will gracefully default to using passwords.

And now you know.