how many machines are on the network? Check the hcp server and make sure the dns address is correct (if present) you may have to manually type in the ip of the dns server for each computer. Also make sure the each machine has the box checked (under tcp/ip properties/advanced) that say register this conections addresses in DNS, and the the server is listed.
What OS is the domain controller running?
What OS are the clients?