Encontrei a resposta e é muito estranha!
Eu usei o comando getprinc em kadmin para obter os atributos do principal do problema e do principal que foi criado sem +needchange e que estava sendo autenticado corretamente.
A diferença era que o principal autenticando corretamente tinha o atributo REQUIRES_PRE_AUTH definido enquanto o principal do problema não o tinha, então a solução é criar o principal desta forma:
kadmin: addprinc +needchange +requires_preauth test_principal