The normal cause of this (in my experience) is a DNS/DHCP issue
When a computer boots on a domain, it sends a broadcast to find its AD site and a DC within that site to connect to.
When it has been provided a DC, the machine will have to check its SID and a machine account password against the DCs records to prove the machine is the one it claims to be and not just dome random machine of the same name (anyone can name a computer "mymachine1" - but that doesn't make it the one that is your domain member).
If your primary DNS is unavailable to perform a lookup for a DC, this can result in delays - meaning the machine account isn't authenticated - which present themselves in this message. Likewise, if a DHCP request takes ages because of multiple hops or a DHCP server availability issue, this can present the same symptoms
Other causes of this can be DC replication problems, the machine being left off the domain (turned off) for extended periods of time or RPC being unavailable on either the client or the DC.
Normally, the reason that it will work again if you give it time is that on failure, a machine will try again after a random short period of time. If your DHCP address has been received, DNS client configured and connected to a dc etc - the check will complete and your machine will then be ready to logon to.
- First off - make sure all your DNS is setup properly. Ideally, your DNS will reside on your DCs and will be replicated with AD.. and your clients will be looking to the DCs for DNS.
- If you have multiple DCs, check which DC your machine is logging onto
each time to help narrow down the search.
- Try manually entering a known good DC as a primary DNS server on this machine
- check the AD object version for this machine on all DCs to rule out replication issues
- manually replicate your DCs to ensure all site links are functional
- check and see if the problem persists with a static IP
- Try the PowerShell Command
Test-ComputerSecureChannel –credential (Get-Credential) –Repair (run as administrator in powershell and give it admin credentials)
- Try a domain disjoin/rejoin for the machine
- Check all group policies are processing on this machine correctly (give it a funky wallpaper via GPO to ensure its processing)
- Is reimaging/rebuilding the machine out of scope?
Hopefully something here will give you a jumping off point.