To check whether or not something is set on the domain level for "log on locally" you will want to go to the Computer Configuration -> Windows Settings -> Local Policies -> User Rights Assignments section of the GPO
This KB article seems to be similar, but not identical to the issue you are having:http://support.microsoft.com/kb/841188
Although it talks about logging into the SBS2003 server itself, not clients...are the old users members of both Domain Power Users and Remote Web Workplace Users groups? Try removing the new users from one of the groups to see if that helps. I guess Domain Power Users and Remote Web Workplace are something they added in SBS2003, because I don't see them on my 2003R2 server.
Also check the Group Policy setting to make sure that there is nothing in "Deny logon locally". It can be found in the section of the GPO I listed above.
Edited by tfitz17, 28 August 2010 - 09:58 AM.