I tried to connect to a brand new Debian squeeze ssh server (no keys setup yet, password authentication) and got this error about too many auth failures.
chris@chris-desktop:~$ ssh [email protected]
The authenticity of host '123.123.123.123 (123.123.123.123)' can't be established.
RSA key fingerprint is 55:b7:aa:9f:14:48:76:50:33:7c:41:11:ee:0c:fd:ef.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '123.123.123.123' (RSA) to the list of known hosts.
Received disconnect from 123.123.123.123: 2: Too many authentication failures for user
I tried wiping .ssh/known_hosts thinking it was due to reusing an IP address and having a stale fingerprint but this did not help.
The problem is caused by Ubuntu's gnome-keyring-daemon which is a helper process that keeps passwords so you don't have to repeatedly re-enter them during a session.
When you try to connect to a new ssh server without an ssh identity file (private key) then gnome-keyring-daemon will offer the server every key it knows in turn and if this is more than the number of tries the server allows then the login process will quit after too many failures before it reaches the tunnelled password login stage.
A simple solution is to kill gnome-keyring-daemon while you are setting up your new ssh server:
chris@chris-desktop:~$ ps -AH | grep keyring
2223 ?        00:00:00   gnome-keyring-d
sudo kill 2223