I have a computer joined to the domain, but it doesn't view the network "location" as being part of the domain. I have tried removing and rejoining the domain and this doesn't help:

Other computers in the same network don't have this problem. I have also tried several different icons, including both the train and the airplane which doesn't seem to make a difference.

At least using nslookup, the server seems to have connectivity with the DCs in the same site. There also seem to be some errors that suggest a NULL domain:

Computer: OR-WEB05.ds.stackexchange.com
Description: NtpClient was unable to set a domain peer to use as a time source because of failure in establishing a trust relationship between this computer and the '' domain in order to securely synchronize time. NtpClient will try again in 3473457 minutes and double the reattempt interval thereafter. The error was: The trust relationship between this workstation and the primary domain failed. (0x800706FD)