Kerberos has (partly?) no support for AES256 on Ubuntu 22.04

I have an issue trying to do a kinit on ubuntu 22.04 with a user that has the "This account supports Kerberos AES 256 bit encryption" checkmark set.

I can kinit without issues to a user that does not have this checkmark set just fine, and weirdly enough, klist shows AES256 as encryption type even for this user:

~ % klist -e
Ticketzwischenspeicher: FILE:/...
Standard-Principal: user1@REALM...

Valid starting       Expires              Service principal
11.01.2023 12:13:58  11.01.2023 16:13:58  krbtgt/REALM@REALM
       erneuern bis 11.01.2023 16:13:58, Etype (Skey, TKT): aes256-cts-hmac-sha1-96, aes256-cts-hmac-sha1-96 

but once I set the checkmark on the user in AD to force AES265 bit encryption, the kinit fails with "KDC has no support for encryption type"

Also doesn't work manually with ktutil:

ktutil:  addent -password -p user2@REALM -k 1 -e aes256-cts-hmac-sha1-96 -f
Passwort für user2@REALM: 
addent: KDC has no support for encryption type beim Hinzufügen eines neuen Eintrags

I tried adding to /etc/krb5.conf the default encryptes:

[libdefaults]
        default_realm = REALM
        default_keytab_name = /etc/krb5.keytab
        forwardable = true
        proxiable = true
        default_tkt_enctypes = aes256-cts aes128-cts des-cbc-md5 des-cbc-crc
        default_tgs_enctypes = aes256-cts aes128-cts des-cbc-md5 des-cbc-crc
        permitted_enctypes = aes256-cts aes128-cts des-cbc-md5 des-cbc-crc

but no change.

Setting the "Do not require Kerberos preauthentication" checkmark to the account doesn't change anything

Manually forcing AES256 on a user WITHOUT the checkmarks works fine as well:

ktutil: addent -password -p user1@REALM -k 1 -e aes256-cts-hmac-sha1-96 -f
Passwort für user1@REALM: 
ktutil:  

But as soon as I set the checkmark to that user, it's broken again.

The issue seem to stem from the november 22 MS updates (https://learn.microsoft.com/en-us/answers/questions/1085603/krbtgt-did-not-have-a-suitable-key)

https://www.reddit.com/r/sysadmin/comments/ypbpju/comment/ivu6aq3/?utm_source=share&utm_medium=web2x&context=3

"The Microsoft programmer has confirmed the November CU patch is incorrectly comparing and negotiating the client/server etypes. https://twitter.com/SteveSyfuhs/status/1590722790663278599 https://i.stack.imgur.com/YlHFO.jpg Recommended workaround is to allow RC4 (or un-setting the GPO settings to use the defaults would also allow for RC4...) for msds-SupportedEncryptionTypes HKLM\System\currentcontrolset\services\kdc\DefaultDomainSupportedEncTypes"

Updating all DCs to the latest version and adding the registry key

reg add "HKLM\SYSTEM\CurrentControlSet\services\kdc" /v ApplyDefaultDomainPolicy /t REG_DWORD /d 0 /f 

to the DCs solved the issue. Installing OOB Update KB5021655 should have solved it too, but seems like it didn't for me (https://support.microsoft.com/help/5021655)