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 accessing the server. This tells the system to check /etc/hosts first for name resolution.
Works for us because there are a relatively small number of workstations accessing this server (<50). And even if I forget to add a new workstation to /etc/hosts, it can still access, it just gets the slow login until I add it in.
Cheers, D.