what error are you seeing in the SQL Server Log? What happens if you add the users directly, or add them to a domain group (Vs. a local group?) Sounds like domain trust/delegation issue...
The probability of survival is inversely proportional to the angle of arrival.