Ran into this long ago when the domain controller was a tempermental NT4 system. The fix was to restart the domain controller service. So, that seems as good a place as any to start.