Windows 7: User profile cannot be loaded (not same as similar-sounding issues)

First, I have read other posts with similar-sounding problems, but they are different. . . .
We have a new Lenovo ThinkPad T510 laptop running Windows 7 and connected to a network domain. A new user usually
can log into our network on a new computer, and a new account is created for them.
On this computer, users whose accounts were set up initially (first day) can log in just fine. However, no user
that does this after the initial setup (e.g., a couple of days later) can log in. We get the following error: "User
Profile Service service failed the login. User profile cannot be loaded."
We have other, identical laptops also running Windows 7 that do not have this problem. We tried restoring and
then reinstalling from scratch. Nothing changed. The weird thing is that it appears to be time-related, in that
users who log in for the first time early-on are fine; ones that login after that run into the problem.
I have read many articles on this error message, but none of them seem to apply. For example, we are not
logging on for a second time (issue with temporary profile, need to delete bad one).
Lenovo support will not help, because it does not appear to be hardware-related.
Does anyone know how to fix this?
Thanks, Alan