In order to connect to your server, clients first need to resolve the server name. In windows, there are multiple ways and protocols used to do this including the SQL Client Network Utility, DNS, Netbios, WINS, Hosts, LMHOSTS, etc.
Got Netbios turned off and no WINS server?
Using the ISP's DNS server and not your own internal DNS server?
Using a NT4 domain and not 2000 Active Directory?