what is your domain architecture? what version of windows server are you using for your domain controllers? when did the problem start? what were you doing when you first noticed the problem? what have you tried already?
If there's a problem with domain authentication, you can usually just remove the affected computer from the domain and rejoin it, to fix the problem, which I suggested in my first reply. Did you try that yet?