Trouble getting a kerberos ticket on RHEL6 when using a kerberos keytab for my AD account

Issue

We are getting inconsistent results when getting kerberos TGTs using keytabs.

$ klist -kte test.keytab
Keytab name: FILE:test.keytab
KVNO Timestamp         Principal
---- ----------------- --------------------------------------------------------
   1 05/16/16 12:03:56 M483168@EXAMPLE.COM (aes256-cts-hmac-sha1-96)
$ KRB5_TRACE=/dev/stdout kinit -kt test.keytab M483168@EXAMPLE.COM
[28462] 1463415496.528345: Getting initial credentials for M483168@EXAMPLE.COM
[28462] 1463415496.533994: Looked up etypes in keytab: aes256-cts
[28462] 1463415496.534066: Sending request (213 bytes) to EXAMPLE.COM
[28462] 1463415496.534149: Resolving hostname ns001.example.com
[28462] 1463415496.580264: Initiating TCP connection to stream 11.120.112.22:88
[28462] 1463415496.580746: Sending TCP request to stream 11.120.112.22:88
[28462] 1463415496.619486: Received answer from stream 11.120.112.22:88
[28462] 1463415496.619541: Response was not from master KDC
[28462] 1463415496.619733: Received error from KDC: -1765328359/Additional pre-authentication required
[28462] 1463415496.619831: Processing preauth types: 2, 19, 16, 15
[28462] 1463415496.619858: Selected etype info: etype aes256-cts, salt "EXAMPLE.COMmdc2vw4046m483168", params ""
[28462] 1463415496.619934: Retrieving M483168@EXAMPLE.COM from FILE:test.keytab (vno 0, enctype aes256-cts) with result: 0/Success
[28462] 1463415496.619983: AS key obtained for encrypted timestamp: aes256-cts/111F
[28462] 1463415496.620089: Encrypted timestamp (for 1463415496.619989): plain 301AA011180F32303136303531363136313831365AA10502030975D5, encrypted AF788888EEA8E53F70B94A5EDA4AA62CC09753FF5BB51C660A9E92A393968AB7C913C4A9C514253F25A3A5B97D602AD86077F28D749268C4
[28462] 1463415496.620113: Preauth module encrypted_timestamp (2) (flags=1) returned: 0/Success
[28462] 1463415496.620124: Produced preauth for next request: 2
[28462] 1463415496.620156: Sending request (293 bytes) to EXAMPLE.COM
[28462] 1463415496.620172: Resolving hostname ns001.example.com
[28462] 1463415496.620853: Initiating TCP connection to stream 11.120.115.52:88
[28462] 1463415496.621239: Sending TCP request to stream 11.120.115.52:88
[28462] 1463415496.798053: Received answer from stream 11.120.115.52:88
[28462] 1463415496.798104: Response was not from master KDC
[28462] 1463415496.798131: Received error from KDC: -1765328360/Preauthentication failed
[28462] 1463415496.798169: Preauth tryagain input types: 2, 19, 16, 15
[28462] 1463415496.798205: Getting initial credentials for M483168@EXAMPLE.COM
[28462] 1463415496.798801: Looked up etypes in keytab: aes256-cts
[28462] 1463415496.798846: Sending request (213 bytes) to EXAMPLE.COM (master)
kinit: Preauthentication failed while getting initial credentials
[m483168@mdc2pr039 ~]$

And here is the output of a successful kinit with an AD account using keytabs...

[p139k1h@mdc2pr039 ~]$ kinit -kt upper.keytab P139K1H@EXAMPLE.COM
[28507] 1463415728.718300: Getting initial credentials for P139K1H@EXAMPLE.COM
[28507] 1463415728.724055: Looked up etypes in keytab: aes256-cts
[28507] 1463415728.724128: Sending request (213 bytes) to EXAMPLE.COM
[28507] 1463415728.724215: Resolving hostname ns001.example.com
[28507] 1463415728.725547: Initiating TCP connection to stream 11.120.115.52:88
[28507] 1463415728.725946: Sending TCP request to stream 11.120.115.52:88
[28507] 1463415728.764364: Received answer from stream 11.120.115.52:88
[28507] 1463415728.764419: Response was not from master KDC
[28507] 1463415728.764569: Received error from KDC: -1765328359/Additional pre-authentication required
[28507] 1463415728.764694: Processing preauth types: 2, 19, 16, 15
[28507] 1463415728.764721: Selected etype info: etype aes256-cts, salt "EXAMPLE.COMP139K1H", params ""
[28507] 1463415728.764804: Retrieving P139K1H@EXAMPLE.COM from FILE:upper.keytab (vno 0, enctype aes256-cts) with result: 0/Success
[28507] 1463415728.764854: AS key obtained for encrypted timestamp: aes256-cts/8B0A
[28507] 1463415728.764963: Encrypted timestamp (for 1463415728.764861): plain 301AA011180F32303136303531363136323230385AA10502030BABBD, encrypted C5628C2E7F6A31EC85343003C6C033EF09CB08622898209B948636DECCFE3C212E029F4C16290BAFC3ED208BBFD3CA86922A987EF68DDBA0
[28507] 1463415728.764988: Preauth module encrypted_timestamp (2) (flags=1) returned: 0/Success
[28507] 1463415728.764997: Produced preauth for next request: 2
[28507] 1463415728.765029: Sending request (293 bytes) to EXAMPLE.COM
[28507] 1463415728.765044: Resolving hostname ns001.example.com
[28507] 1463415728.765727: Initiating TCP connection to stream 11.120.112.22:88
[28507] 1463415728.766139: Sending TCP request to stream 11.120.112.22:88
[28507] 1463415728.806953: Received answer from stream 11.120.112.22:88
[28507] 1463415728.807004: Response was not from master KDC
[28507] 1463415728.807096: Processing preauth types: 19
[28507] 1463415728.807110: Selected etype info: etype aes256-cts, salt "EXAMPLE.COMP139K1H", params ""
[28507] 1463415728.807119: Produced preauth for next request: (empty)
[28507] 1463415728.807165: AS key determined by preauth: aes256-cts/8B0A
[28507] 1463415728.807296: Decrypted AS reply; session key is: aes256-cts/C537
[28507] 1463415728.807306: FAST negotiation: unavailable
[28507] 1463415728.807410: Initializing FILE:/tmp/krb5cc_71092372 with default princ P139K1H@EXAMPLE.COM
[28507] 1463415728.807579: Removing P139K1H@EXAMPLE.COM -> krbtgt/EXAMPLE.COM@EXAMPLE.COM from FILE:/tmp/krb5cc_71092372
[28507] 1463415728.807595: Storing P139K1H@EXAMPLE.COM -> krbtgt/EXAMPLE.COM@EXAMPLE.COM in FILE:/tmp/krb5cc_71092372