the target has a host/
but ssh fails with:
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password debug1: Next authentication method: gssapi-keyex debug1: No valid Key exchange context
Well the first thing to realise is that you're probably not using gssapi-keyex, you're probably using gssapi-with-mic (see http://www.ietf.org/rfc/rfc4462.txt if you want to know more).
/usr/bin/sshd -D -ddd -emay give
debug2: input_userauth_request: try method gssapi-with-mic debug3: mm_request_send entering: type 38 debug3: mm_request_receive_expect entering: type 39 debug3: mm_request_receive entering debug3: monitor_read: checking request 38 debug1: Unspecified GSS failure. Minor code may provide more information Key table entry not found
The problem I has was a typical one in kerberos setups... DNS and name resolution has to work.
In this case a simple entry in the hosts file with a non-fqdn and there are very few clues.
So maybe you'll google some of that and it'll help... :)