An entry in hosts helps only if the DNS is not working at all. For browsing, either a DNS server responsible for the Active Directory needs to be contacted, or a WINS server, to ask for NetBIOS services like the Server services we need here, or a broadcast is done otherwise. From the delay I reckon the broadcast is eventually supplying the server.
First check if DNS is asked at all for any name with nslookup nls1, then ping the name (and pay attention to the duration of name resolving there). nslookup is directly asking DNS server, while ping uses the DNS cache service, which is sometimes confused and needs to be restarted to get working again (however, I only experienced that on Vista yet).
If you can't find out the source of the failure, a workaround is to either use LMHOSTS with a #PRE #DOM entry for the domain controller, or to start a WINS server. Using a (AD integrated) WINS server will help resolve NetBIOS names much faster, if DNS can't be queried for some reason.
