Cross realm breaks in one direction

[Booker Bense]

Any experience with 
USGCB (US Gov Computer Baseline) settings for windows systems?

Our windows admins recently applied these settings for windows systems and the
cross realm trust with our unix based KDC has broken in the direction of getting 
unix KDC service tickets with windows credentials. The other way still works just fine. 

The error a client gets is "KDC does not support enctype".  Looking at the logs, it does not appear
that the unix KDC ever gets contacted. 

A list of possible suspect changes are 

Microsoft network client: Digitally sign communications (if server agrees): Enabled

Microsoft network server: Digitally sign communications (always): Enabled
Microsoft network server: Digitally sign communications (if client agrees): Enabled

Network security: LAN Manager authentication level: Send NTLMv2 response only. Refuse LM & NTLM
Network security: LDAP client signing requirements: Negotiate signing
Network security: Minimum session security for NTLM SSP based (including secure RPC) clients
        Require NTLMv2 session security: Enabled
        Require 128-bit encryption: Enabled
Network security: Minimum session security for NTLM SSP based (including secure RPC) servers
        Require NTLMv2 session security: Enabled
        Require 128-bit encryption: Enabled
Network security: Configure encryption types allowed for Kerberos
        DES_CBC_CRC: Disabled
        DES_CBC_MD5: Disabled
        RC4_HMAC_MD5: Enabled
        AES128_HMAC_SHA1: Enabled
        AES256_HMAC_SHA1: Enabled
        Future encryption types: Enabled

Everything in the software stack should support  AES256_HMAC_SHA1 and that's the enctype used for 
everything in the get WIN service tickets with unix tgt's case. 

Doing the obvious thing of enabling DES didn't fix anything. Any suggestions? 

thanks, 

- Booker C. Bense