You might try uninstalling and reinstalling Kixtart on your Domain Controller(s). I'm hoping this isn't an active directory incompatiblity with the kxrpc, because we are intermittantly seeing the same issue. We've reinstalled kxrpc on the dc's by running the following command from \winnt\system32:
code:
kxrpc -remove
Then:
code:
kxrpc -install
net start kxrpc