First a tutorial on how Windows Authentication works.

A user logs into his/her computer. That computer is part of a domain and the user's login is authenticated by the domain controller. Then when they connect to SQL Server on the same domain, the domain controller still recognizes their login credentials. But if SQL Server is on a different domain, that domain controller may not recognize the login so the access fails.

Therefore, in your situation....

Are the users and the SQL Server still on the same domain?

If so, go to Enterprise Manager, expand down to Security, click on Logins and see what it shows as the path for the failing logins. If it's not the correct path, you will have to redo them (I believe you can use the Copy function - right click on the login).

If not, then you need to have both domain controllers update each other with the user information.

-SQLBill