Incompatibility between krb's AES256-CTS-HMAC-SHA1-96 and Microsoft Windows Domain

[Ido Shlomo]

I am trying to upgrade our system's kerberos encryption from RC4 to AES256.
I've set up a Microsoft Windows Domain user with AES256 encryption support.
I'm creating a keytab for kinit using ktutil on Linux:

ADD_ENTRY="addent -password -p $DOMAIN_LOCAL_USER@$DOMAIN_UPCASE -k 2
-e AES256-CTS-HMAC-SHA1-96\n$DOMAIN_LOCAL_PASS\n"
echo -e "$ADD_BASE_ENTRY\n$ADD_ENTRY\nwkt user.keytab\nquit\n" | ktutil

kinit works well with that keytab.

However, when I'm creating an SPN for this user using ktutil on Linux

ADD_BASE_ENTRY="addent -password -p
MSSQLSvc/$SHORT_HOSTNAME.$DOMAIN_LOWCASE@$DOMAIN_UPCASE -k 2 -e
RC4-HMAC\n$DOMAIN_PASSWORD\n"
echo -e "rkt spns.keytab\n$ADD_BASE_ENTRY\n$ADD_ENTRY\nwkt
spns.keytab\nquit\n" | ktutil > /dev/null 2>&1

then I'm unable to accept incoming connections using krb 1.15.2:

GSS-API major_status:000d0000, minor_status:000186a6
GetGSSError(): GSS Error ERR_MAX: Unspecified GSS failure.  Minor code
may provide more information
GetGSSError(): GSS Error ERR_MIN: Request ticket server
MSSQLSvc/greensqlcent21.kerberosdc.msft:1434 at KERBEROSDC.MSFT kvno 2
enctype aes256-cts found in keytab but cannot decrypt ticket

This has worked well when I was using RC4_HMAC for everything.

*Some background:*

My application mimics an MSSQL server. I'm running as a User (not as the
computer) and I have set this user to login with AES256. Initially, I have
kept the SPNs in the incoming keytab file with RC4_HMAC (this used to work
when the domain user was also authenticating using RC4_HMAC), but I got an
error that the gssapi accept function is looking for an AES256 entry in the
SPN keytab file. So I changed the SPN keytab file to also use AES256 and
got the above error.

Tested with both Windows 2k8 and 2k12 as Domain Controllers. Both fail.