This was an odd one. Recently I was setting up key-based ssh access for a server and the client was failing to connect with the generic "Permission denied (publickey,gssapi-keyex,gssapi-with-mic)." error.
I checked the server log (Centos, so /var/log/secure) and found an interesting "error: hash mismatch" message.
Using -v to get debugging info on the client end also gave me a message of "key_parse_private2: missing begin marker" - this was a red-herring and I suspect it happens often even when connections are working just fine.