I have had a whole rush of SSH login problems that I finally figured out thanks to the Ubuntu forums. There are a number of symptoms including these debugging messages when logging using ssh -vvv server:

debug1: An invalid name was supplied
Configuration file does not specify default realm

debug1: An invalid name was supplied
A parameter was malformed
Validation error

debug1: Miscellaneous failure
No credentials cache found

What happens is that SSH will hang for a long period of time before providing a password prompt or performing key authentication. In either case the problem is the GSSAPI that is now being used by clients and not by most servers.

The fix is simple. Open up /etc/ssh/ssh_config and comment out this line:

#    GSSAPIAuthentication yes

This should turn off the client using GSSAPI and the hanging/timeouts should stop.