Did you upgrade from 1.2.x to 1.3.1 between now and when things stopped working? If so, the default master key enctype for 1.3.1 is different from the enctype for 1.2.x. So you may need to explicitly specify the master key enctype in your kdc.conf if you have an old realm.