If it's the same users that seems to run into this problem, then I would suspect their profiles or security rights as the issue. The issue is not limited to one machine, and you can (at least temporarily get around it) so would NOT recommend messing around with the computer and its domain setup. I would instead try the following:
1. Login as an Administrator
2. Delete the profile of the failing user account
3. Restart the machine and login under a NON-FAILING account that has NOT logged into this computer before.
ASSUMING THIS USER LOGS IN PROPERLY:
If all is OK at this point, then the default user profile on the machine is working OK. Now, restart the machine again and try logging in as a FAILING USER. The desktop should come up and both LOOK and WORK properly. If it doesn't come up at all or the desktop looks different that the last user, then you're using some type of ROAMING PROFILE in your network and that's probably where your problem lies. I haven't worked with roaming profiles but, as I said earlier, things like differences in hardware and shortcuts to hardware-specific locations within the profile would cause the desktop to lock.
ASSUMING THIS USER DOES NOT LOG IN PROPERLY:
If it FAILS like the others, then your default user profile is bad on this machine and you need to re-do it. Easiest way to do that, if available, would be to copy a working profile as DEFAULTUSER under the Advanced tab of the System Control Panel. If you don't have a working profile available, I've always just started from scratch with the OS. There's probably a way to copy a profile from another system but I've never done it.
Hopefully, this test will at least narrow the list of suspects.