No matching key in entry means that you included an encrypted timestamp with an enctype that the KDC couldn't find for the key. Do principals that work have a different set of encryption types than principals that fail?