In addition to making sure that the workstations have the WINS server's address in their TCP/IP settings, I'd try forcing the workstations into H-node. I'm not sure how to do this manually (supposedly setting a WINS server name in TCP/IP settings does this, but I don't trust it). I always use the DHCP WINS/NBT Node type scope option to do this. If you are using DHCP, simply go to the scope options, add the WINS/NBT Node type option and select 0x8 (H-node) as the setting. (Then make sure to wait until the workstations have renewed their DHCP leases - or force the lease renewal - before expecting any change in behavior!) This will ensure that the workstations try using the NetBIOS name server (i.e., WINS server) first, then broadcast, and then DNS. This SHOULD speed things up if the problem is, in fact, that the workstations are trying to use DNS first (which is very often the cause of this type of slowness in name resolution). Assuming that the problem isn't simply that your WINSserver is overloaded and can't respond quickly enough. . .
P.S. If having an LMHOSTS file doesn't help then something must be wrong with your LMHOSTS file, or the workstations are not set to use the LMHOSTS file. Normally, if a workstation is operating with all three options set - WINS, LMHOSTS and DNS - it will try using the local name cache first, which is where the LMHOSTS information is stored.
Hope this helps!
