Will, you're a little too helpful I'm not ready to reply
to the list and provide the summary of what the solution to
my original post was. Strange that you are ... for me!

A bit premature.

Using short hostnames did not solve the problem.

Fixing /var/krb5 on the single box that was missing it
did not solve the problem.

The problem is not solved.

And replying to your last email to me (which was not sent
to the list), pkgchk -n shows absolutely nothing of any
relevance to the problem. These are not hackish boxes
in random unknown states with 20 admins screwing around
with them weekly. They're jumpstarted, patched at that
time with the Recommended cluster, no users have root
privs, and skew is overridden nightly via cfengine.