I tried to get a linux box to be friendly to an exchange 2003 server using kerberos.
The kinit -k username failed with:
kinit(v5): Key table entry not found while getting initial credentials
and I was going nuts.

Solution: I did not pass the right enc type to the ktutil addent command.

Here's what I did to get it finally working:
addent -password -p username@MYREALM -k 1 -e arcfour-hmac-md5

If you're not sure, run a
klist -e
and take a look at the encryption there.
In my case, it says: Etype (skey, tkt): ArcFour with HMAC/md5, ArcFour with HMAC/md5