John Devitofranceschi helped us narrow down this problem to the use 
of explicit salts when the key data uses the default salt.

We intended to start always sending explicit salts in 1.7 (#6470) but 
didn't actually succeed until 1.11.  The stated rationale for sending 
explicit default salts was pretty; after doing some testing I can 
clarify it to this: when the canonical name differs from the 
requested name and encrypted timestamp/challenge preauth is required, 
an explicit salt must be communicated to the client, or the client 
(at least, our client) will compute the wrong default salt.  When 
preauth is not required, the client uses the canonical name from the 
KDC-REP to compute the default salt, so an explicit salt isn't really 
needed.

We could narrow the use of explicit default salts to scenarios where 
client principal aliases were used, but it would require more state 
to be communicated into the KDC preauth code.