The subject behavior will occur if you chose Permissions compatible only with Windows 2000 server in Dcpromo.exe and clients are running Windows NT 4.0 with SP4 or earlier.

The recommended fix is to apply SP6a, but you can also perform the following on the SP4 (or earlier) workstations:

Open a CMD prompt and type:

net localgroup "Pre-Windows 2000 Compatible Access" everyone /add