Nicht alle Domänenbenutzer können sich am Client anmelden

Hallo zusammen,

ich habe von meinem Chef die ehrenvolle Aufgabe bekommen, als ungelernter ein Netzwerk zu betreuen.
Dieses Netzwerk wurde leider schon vorher von Leuten mit ähnlichem Hintergrund betreut.
Es tritt nun folgendes Problem auf:
An mehreren (neuen) Client Computern kann sich nur der Domänenadmin (ich) einloggen, aber kein Domänenbenutzer.
Die Domänenbenutzer wurden zuvor im Server (Windows 2008) angelegt. Das Häckchen,
dass sich diese User an allen Clients einloggen können ist gesetzt.
Eine mehrstündige google-Suche erbrachte keinen Erfolg (vielleicht habe ich auch einfach nur nach den falschen Stichwörtern gegoogelt).
Es erscheint die Fehlermeldung: "Es sind momentan keine Anmeldeserver zum Verarbeiten der Anmeldeanforderung verfügbar."
Diese Fehlermeldung erscheint auch, wenn man einen Usernamen eingibt, der nicht in Windows Server registriert ist (Phantasiename).
Wenn ich versuche auf dem Client einen Domänenbenutzer manuell hinzuzufügen (ich dachte es liegt am Client), erscheint die Fehlermeldung:
"Der PC kann im Moment nicht mit der Domäne kommunizieren. Versuchen Sie es später nochmal, oder fragen Sie Ihren Domänenadministrator."
Der PC ist allerdings schon in der Domäne und ich als Domänenadmin darauf angemeldet.
An manchen älteren PCs können sich nur der Domänenadmin und der Benutzer einloggen, der den PC schon immer besitzt.
Das Problem erstreckt sich sowohl auf Domänenbesitzer "vor meiner Zeit", als auch welche, die ich angelegt habe.
Habt Ihr vielleicht einen kleinen Tip woran das liegen könnte, bzw. die richtigen Schlagworte für google?
Vielen Dank!
Euer brewersgold