I also just found some clues that it might be caused by reverse DNS: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409360
Disabling mdns4 hosts lookup in /etc/nsswitch.conf indeed seems to fix the problem, so I will probably settle with that workaround, keeping GSSAPIAuthentication turned on.
I also just found some clues that it might be caused by reverse DNS: http:// bugs.debian. org/cgi- bin/bugreport. cgi?bug= 409360
Disabling mdns4 hosts lookup in /etc/nsswitch.conf indeed seems to fix the problem, so I will probably settle with that workaround, keeping GSSAPIAuthentic ation turned on.