Roughly the same effect, but not exactly -- without knowing what's causing the problem, it's rather hard to tell exactly what'll fix it.
One thing occurs to me: check the file /Library/Preferences/edu.mit.Kerberos, and see what's listed as the kdc address (in the \[realms\] section, not in \[logging\]). Under some circumstances, this can get bogus entries listed, which means the clients may need to make several tries before finding a valid address for the KDC.
If that's the problem, destroying & repromoting should fix it, as would swapping replicas. Or, if you're feeling daring (and have backups of everything important), you could try to edit it directly: In Workgroup Manager's preferences, enable 'Show "All Records" tab and inspector, then select "All Records" (the bullseye tab that just appeared to the right of users, groups, computers, and computer groups tabs), then "Config" from the pop-up menu under that, then KerberosClient from the list under that, then "XMLPlist" on the right, then "Edit" below that (if you don't have an Edit button, you may need to authenticate to the domain first). You're now editing the XML property list that edu.mit.Kerberos is created from (maybe you should copy it into a text file in case something goes wrong); you need to remove bogus entries from the arrays under the KADM_List and KDC_List keys, then increase the generationID by one. Then run "sudo kerberosautoconfig" on a client to force it to update, and test again.
