This error can be caused by a few different reasons. In this particular case it’s a Centos 6 server connection to a Microsoft Active Directory 2016 DC. The short version of the story is that even though the FQDN has a valid key in the krb5 keytab it will only properly authenticate using the short name (pre-2000 name). This can be done by changing the hostname but I find it better to force it in the /etc/sssd/sssd.conf in the domain section:
ad_hostname = THISISVERYLONGD
ad_domain = EXAMPLE.COM
That will force SSSD to use the short name.