Your first error message is mentioning that " AES256 CTS mode with HMAC SHA1-96 is not supported/enabled". Java is a little bit frustrating in that, the standard distribution from Java does not enable all security algoritms. The strongest algoritms are by default disabled.
The encryption method that your new kerberos server is requesting is not yet enabled in your Java. (Most HMAC methods aren't enabled by default).
You have to download the Java JCE unlimted strength policy. This will enable this encryption method. This download is a simple zipfile with 2 jar files in it. Extract that zip file, and paste the two jar files in your java library folder (c:/program files/java/bin/). There should already be a file with the same name and you can overwrite those two. All this does is allow for more encryption methods. http://www.oracle.com/technetwork/java/javase/downloads/jce-7-download-432124.html
Some context why SAML and Ldap don't have this issue, the libraries used by Ldap and SAML are more modern than the java-kerberos library. And these libs leverage a third party library called 'BouncyCastle', that lib provides a workaround for this security problem.
Unfortunately with for example the FTP, and Kerberos module there is no compatibility with the BouncyCastle library and you'll have to update the Java JCE policy.
Keep in mind with every Java version upgrade you'll have to re-enable the JCE policy
We have tried the JCE policy (see my try 3).
We did it for Java 6 and java 8. Should the standard -crypto option or the AES256-SHA1 be used for Win2012? Both did not work for me on Win2012.
Update:
It is now working. Not sure what did the trick. But the keytab file is regenerated with default -crypto (not provided to the command). After that it worked without any issues.
The JCE policy files are used.