TS login problems after upgrading to sp4

I admit to being somewhat baffeled and up that specific creek, no paddle in sight. My case is this: after upgrading to sp4 on a PDC with Terminal Services SOME clients are experiencing trouble logging in. This seems to affect ONLY clients running windows pre XP! And to add to this strange behaviour: after some time, the situation seems to resolve itself, in the sense that with NO tweaking or action at all - anywhere - suddenly they get access!

I have checked everywhere, but so far to no avail.
As for any error-messages or indication as to what may be going on: nothing. They seem to get as far as to the logon on server, but are kicked straight back out after entering password.

Anyone of you folks able to lend a hand? Would be much appreciated!

Um... seems i forgot to point out that this is on an W2000 Server. Old stuff.