When you add the users individually, are they still connecting via NT authentication? After logging into the server, execute the following query:
SELECT SUSER_SNAME()
This will return the login name of the user. If you're using NT Authentication, it should look something like DOMAIN/username.
BTW, what's the server's error message?
-Mike