Разобрался почему у меня раньше не удавалось сделать Single Sign On с использованием Kerberos и шифрования сеансовых ключей в AES-256. При этом, шифрование в RC4 работало без нареканий. Как выяснилось, Windows Server 2012 R2 из коробки поддерживает и AES128, и AES256, но по умолчанию они выключены. Чтобы включить, надо для аккаунта установить флаг, см. скриншот.
Если хочется ключей с шифрованием AES-256, то подобную процедуру нужно проделать для каждого пользовательского аккаунта и для каждого сервиса, который должен аутентифицировать этих пользователей.
Народ с "serverfault.com" советует использовать для этого вот такой Powershell-скрипт.
Почему нельзя было включить эти возможности по умолчанию, лично для меня остается великой загадкой.