Quando tudo mais falhar, jogue um sniffer de rede nele. Dê uma olhada no que realmente está acontecendo na conexão enquanto um computador cliente está esperando, talvez você possa ver o que realmente está esperando.
EDITAR:
BTW, você usa o WINS na sua rede? Isso também pode ser um problema de resolução de nome NetBIOS. Os clientes do Windows 98 / NT gostam de usar isso em vez de DNS, e sem o WINS ele tentará resolver nomes usando consultas de difusão, o que pode ser um problema real nos horários de pico de uso da rede.