Hey there,
It's not DNS, so don't worry about anything in that or restarting that service. Network Browsing is based on NetBIOS, it's all legacy stuff and a bit temperamental.
First things first.
On your server ensure that NetBIOS over TCP/IP is enabled in the TCP/IP Settings / Network Settings.
Then ensure that the Computer Browser Service is started.
The server must announce it's presence to the Master Browser on the network to be visible in the Browse List (and therefore in Network Places). To improve reliability of the Browse List it would be a good idea to make sure your Server is the one that hosts it.
That's a simple case of adding a registry value to your server. It's documented here:
http://www.microsoft.com/technet/prodtechnol/windows2000serv/reskit/cnet/cnfi_brs_vcer.mspxIt's the IsDomainMaster value we're particularly interested in.
If you have more than one IP Subnet a WINS Server is required, all clients and servers must be told to refer to that.
HTH
Chris