Eu me deparei com o mesmo problema (mesmas versões do Debian e do krb5-admin-server).
O mesmo que você, ele não estava funcionando quando eu corri o kadmin do próprio servidor admin do kerberos, que descarta as diferenças de tempo (eu até instalei o NTP para ter certeza - não fazia diferença no problema).
No meu caso, a questão acabou por ser de entropia. O Kadmin sendo muito seguro requer muita entropia para gerar as chaves de sessão.
Minha configuração (uma configuração de teste) está sendo executada em máquinas virtuais. Eu acharia que não poderia kadmin em tudo, mas depois de cerca de meia hora kadmin iria 'misteriosamente' começar a trabalhar.
Você pode verificar a entropia do sistema em:
/ proc / sys / kernel / aleatório / entropy_avail
Para remediar o problema, fiz uso da entropia do computador host (/ dev / random), e usando o rng-tools, tornei isso disponível para o kadmin.
Como um aparte, para a solução de problemas gerais do kerberos, você pode ver:
Algo como o seguinte enviará o log de rastreamento para a stdout, permitindo que você veja o que está acontecendo em detalhes:
env KRB5_TRACE=/dev/stdout kadmin -p johndoe/[email protected]