In my experience 80% of the time this is a DNS problem.
Check it by explicitly setting the IP for your Preferred DNS server inthe connection on one of the slow machines and see if that fixesit. If so, you can leave it that way (possible GOTCHA! down theroad, tho...), or go find out why the...