A Domain relies entirely on a DNS server for name resolution.
I assume you are running DNS on one of your servers in your Domain, even if it's your Domain Controller.
Make sure that all Domain Client machines are point at your local DNS server for name resolution. As a matter of fact it should be the only DNS server they have or need in the properties of IPv4 in the properties of their individual network adapters.
You can of course add a WINs server but it should not be necessary.