Smart Card Logon failure KDC certificate CERT_TRUST_IS_NOT_VALID_FOR_USAGE

We are trying to enable Smart Card Logon.

When we attempt to logon with a Smart Card we get "The Kerberos Protocol encounterd an error while validating the KDC certificate during Smart Card Logon."

In the system log we see the following event:

Event ID 9
The certificate is not valid for the requested usage.
The client has failed to validate the Domain Controller certificate for DC.domain.com. The following error was returned from the certificate validation process: The certificate is not valid for the requested usage.

Looking in the CAPI log we see that the domain controller cert is passing the CRL checks, but is returning:
CERT_TRUST_IS_NOT_VALID_FOR_USAGE

We are using all 3rd party certificates.
The CA certificates have been added to the correct CA stores via Group Policy.
The root is in the Trusted Root Certificate store.
The 2 intermediate CA's are in the Intermediate CA store.

The CA certificates have all be added to the NTAuth store.

All the domain controllers have certificates, issued by the above CA's.

The smart card certificates are issued by the above CA's.

certutil -urlfetch -dcinfo verify says the KDC certs on all of the domain controllers are valid.

I can't figure out what I'm missing.   Why are the clients not trusting the domain controller certificates for the required usage?