On any workgroup/domain installation, I setup DDNS (with acceptance of dynamic registration) on my server at the bare minimum. Sometimes, that isn't enough (depending on the client OSs) so I put WINS on as well with DNS-to-WINS query enabled. Then, all the workstations look to my servers ONLY for name registration and resolution. This also notifies the clients coming online of what servers/resources are available and where to find them. Do you have either of these setup on your server? Are you running Active Directory?