Apache Kerberos Authentication : KDC has no support for encryption type
Solution 1:
It was indeed due to the activation of the DES support in AD. This actually override any other cipher algorithms.
So disabling it on the service account made the negociation works in AES256.