It sounds like an AD problem. How many DCs? Have you tested \\domain.tld\netlogon\ instead of the DC name?
Maybe force the wait for network GPO. Clients may be logging on with cached creds and not waiting for the network.
Check your network providers and order for possible need to tweek.
_________________________
Give a man a fish and he will be back for more. Slap him with a fish and he will go away forever.
