We had this problem and found it was related to our DNS servers. They didn't want to mess with those, so what we did was in /etc added a file netsvc.conf with a line in it "hosts=local, bind" (without the quotation marks). Then added a line to /etc/hosts for every workstation...