O servidor já lhe disse a resposta.
Então, você precisará identificar duas coisas:
1) Por que tipos de criptografia o cliente suporta?
1) Por que tipos de criptografia o KDC suporta?
Poste seus clientes krb5.conf e o servidor kdc.conf e informe o uso do SO dos clientes.
FWIW dê uma olhada aqui: link