I was able to get around the problem you are describing with Server 2008 by changing the default domain controller policy to allow cryptography algorithms compatible with Windows NT 4.0. I believe the policy is located here:
Default Domain Controller Policy-->Computer Configuration-->Policies-->Administrative Templates-->System-->Net Logon
If i think security this is not wise move. I am scared what our organizations domain admin will say when we upgrade to w2k8 domain and i ask to change this policy.
Any developer who wants say something about this problem?