I noticed this in my clients' system logs:
5/14/11 11:00:51 PM SecurityAgent[2735] User info context values set for testuser 5/14/11 11:01:12 PM authorizationhost[2734] k5_authenticate(): got -1765328228 (Cannot contact any KDC for requested realm) on /SourceCache/SecurityAgent/SecurityAgent-39574/plugins/krb5/krb5_operations.c:84 5/14/11 11:01:12 PM authorizationhost[2734] -[SFBuiltinAuthenticate performDSPasswordAuth](): got -1765328228 (Cannot contact any KDC for requested realm) on /SourceCache/SecurityAgent/SecurityAgent-39574/authhostbuiltins.m:1039 5/14/11 11:01:13 PM SecurityAgent[2735] Login Window Showing Progress
KDC is running on the server, but the firewall ports were blocked. I unblocked the KDC ports (TCP/UDP 88) by going into Server Admin > Firewall > Settings > Services > Allow: Kerberos V5 KDC
, and now network login takes only 5-10 seconds, same as local accounts.