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.