Network location is not on the Domain

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)

That error suggests you could have a bad computer password. Can you remove and readd to domain without breaking server apps? (don't know what's on the server).

The icons for Network Location are purely aesthetic.

Note there is a hotfix that may resolve your NLA issue.

More info on NLA.

Network Location of "Domain" is determined by DNS search suffix and AD connectivity. To ensure DNS isn't the issue, and assuming since it's a server, that you've set IP statically: you need to ensure the TCP/IP DNS settings have the same DNS suffix as the AD DNS domain. Normally you leave this blank in the NIC IPv4 DNS tab and let the computer domain membership match your DNS server settings (System -> Advanced System Settings -> Computer Name -> More -> "Primary DNS suffix of this computer"). Just pair up this setting and NIC settings to a work server to be sure they are correct.