Similar to http://www.macwindows.com/tutwinnt.html you not only give them accounts but the Services for Macintosh has us put them in the right group and more.
Just asking. Did you inherit this server? I find that when this question is asked, the IT staffer is taking over for the old retired staff that didn't document the procedure.
And if that link does not help it's not because it doesn't apply. It may not apply to your setup. You'll have to find out what differs from old and new accounts.
I have a Windows 2000 server which had been working fine until recently. When I set up new users, they are not able to connect from a MAC OS9 machine. It returns an invalid username and password. This is consistent with the Windows 2000 server which returns the same in event viewer. Weirdly though, the user is able to log into the Windows 2000 server from a Windows machine with the same user name and password.
In addition, old accounts work just fine with both MAC and Windows Clients. I have uninstalled the latest security patches, but still no luck...