This confusing looking error really means, "Password incorrect" (and in fact
it's the error that kinit looks for when it goes to print the "Password
incorrect" message). It means that the encryption key used to encrypt the
data in this message didn't match the encryption key used for decryption,
and as a result the checksum comparison didn't work.

The most common time I've seen this message is when trying to set up a slave
KDC. In this case, the two keys that don't match are the encryption keys for
the host principal that are stored in the KDC database and on the slave.
This is generally caused because the administrator was confused about the
location of host keys and put both host keys on both machines (the master
and the slave). Unfortunately, this causes problems because every use of
ktadd generated a new key (see Question 2.9 for more information). The
solution in this case is to delete the keytabs on each machine, and only add
the host principal's key to their corresponding machine; e.g., add
host/master.your.domain ONLY to your master KDC and add
host/slave.your.domain ONLY to your slave KDC.

In general, this means that the encryption key stored in a keytab doesn't
match the key stored in the KDC for a particular principal. As mentioned
above, generating a new key will fix this problem. Note that you'll need to
get rid of any old cached tickets by using kdestroy, otherwise the various
Kerberos programs will continue to use an old ticket encrypted with the
wrong encryption key.