As an additional suggestion, be sure the spooling on the print server is NOT located on the same drive as the operating system. I have had print servers crash because they ran out of operating space as users dumped a few 500+ MB power point print jobs at the same time, and believe me, it is not prretty to try to recover a server with 0 bits of drive space left!
To pin point your problem when the users can not print, can they ping the print server (by name, not ip address)? If not, you have a WINS issue or a DNS issue to resolve, as this gets information updated when you reboot the server and it announces itself to the network. If the user cannot ping the print server, then I agree with jpondel.
Make sure also that the print server (and all other servers) are using fixed addresses that are excluded from the dhcp ranges.
With a DOmain, you should make the DC the DNS server for your Domain, point all users to the Domain DC for DNS. Make sure you have pointed the DC DNS to itself first, the to the outside DNS sources second. This way all users will be able to resolve the internal print server name correctly.
Important note, however, do not forget that if any of your users are on older operating systems such as WIN98, then you MUST have a WINS service running for them to resolve the printer address everytime they log on. Put this on the DC also.
HTH
David