Extrem langes Durchsuchen des Netzwerkes und dann keine Berechtigung?

Hallo, ich schlage mich seit einiger Zeit mit folgendem Problem rum:

Ich habe ein Netzwerk mit 6 Rechnern und einem Server eingerichtet, der die Internetverbindung verwaltet und außerdem einen Netzwerkdrucker bereitstellt.
Wenn ich von meinem Rechner aus auf die anderen via Netzwerkumgebung zugreifen will, dauert es zunächst ewig (ca. 2 bis 3 Minuten), bis ich in den Dialog "Microsoft Windows Netzwerk" gewechselt habe, wo dann die eine Arbeitsgruppe angezeigt wird. Wenn ich darauf zugreifen will, dauert es wiederum 2 bis 3 Minuten, bis die Meldung erscheint, ich hätte keine Berechtigung, darauf zuzugreifen, was aber Blödsinn ist, da alle anderen Rechner mit der gleichen Konfiguration das anstandslos machen, vor allem ohne diese fette Verzögerung.

Hat jemand eine Idee?

Systeme:
Rechner 1-6: Windows XP, einige DHCP, meiner feste IP
Server: Ipcop (Linux-basiert), mit DNS-Dienst und Samba, alles da