Are you trying to add users on a Domain Controller or on a
workstation using AD tools?
I have seen one instance of this where the workstation was added to
the domain on a domain controller and the machine account didn't
replicate to other domain controllers in the domain. When trying to
create a user, the workstation couldn't validate it's machine account
to any other DC and thus couldn't create any users.
If you are adding user accounts from a workstation, try disjoining
and rejoining the domain.
Tom Ausburne (MSFT)
Windows 2000 Directory Services
This posting is provided "AS IS" with no warranties, and confers no
rights.