Cross realm Kerberos Trust - Active Directory <-> RHEL9

We are migrating our CentOS8 MIT Kerberos infrastructure to RHEL9. Everything is working except for Kerberos access from the MIT realm to Active Directory.

Flow

Client (centos8) gets ticket from RHEL9 KDC
Client executes a ldapsearch using Kerberos credentials against Active Directory
Search fails with ldap_sasl_interactive_bind_s: Local error (-2)

Reviewing the tickets the client gets the ticket from the trust principal inside the MIT KDC for the AD domain. Watching the transaction in wireshark the request for the ldap/ad_domain_controller service ticket fails. The error text inside wireshark is Generic Error.

AD does have events that go along with the search that lead to incompatible encryption types. The DCs are configured for AES128 and 256. The trust principals in the MIT KDC are AES128/256

Any thoughts on what the issue might be?