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