EDIT 1 - This is still an issue for us, and I thought I'd bring up the topic of preinstalled software, notably Intel Wireless Manager. I have a feeling this is at the very least contributing to the issue, but when I tried to remove it it removed the wireless drivers completely.
After much Googling, it seems I can't string together the right phrase to find what I'm looking for, so here it is.
I just helped one of my users that was unable to log in. What seems to have happened is that the cached authentication on his workstation had expired, and there was no network connection at the login screen for him to successfully reauthenticate. As a result it was telling him that his user account did not exist. To fix this I had him log into the local user profile that we use for servicing, connect to the network, then switch user so that he could use his domain account. Once he was able to login to his domain account we were able to log the local account out, and his domain account is now able to log in and out with no issues thanks to a refreshed authentication cache.
What would be causing my workstations to not have a network connection without a user logged in? This is normal for our network, too. Since I didn't set it up initially I have no idea what would prevent network connectivity without a logged in user.
Our workstations run Windows 7, and the onsite servers at our locations are all running Windows 2008 R2 Standard. If any other information is required I'd be glad to obtain and provide it.
1.Cached logons don't expire AFAIK. Windows will cache the last 10 unique logons, which would imply in your case that 10 unique user accounts were able to successfully login to the domain, thereby "flushing" this users cached logon. If that's not the case then there's something else going on, unless I'm completely misunderstanding cached logons.2.I don't understand how simply logging on as a local user restored network connectivity. Can you clarify this?