One of the servers I support started acting up after the office network was restructured (another router and new switches). Checking the Event Viewer turned up frequent occurrences of a NetBT Error 4319. Googling this error brought me to the knowledge base article Event ID 4319: Duplicate Names on the Network.
The culprit turned out to be the Domain Controller itself, it had two NICs that both got connected when the network was reconfigured. Because there was only one machine name and each NIC had a separate IP address the other computers were reporting that there were two machines with the same name.
For now the second NIC is not needed so simply unplugging it fixed the problem but if it was needed the problem could likely be resolved by making sure the server had a unique machine name for each NIC or placing the NICs on separate VLANs or separate subnets.