One thing you can take a look at is the ISAPI filters on the actual Virtual Server or Web Site in IIS. I have seen issues where a citrix or another programs ISAPI filter is placed above stsfltr in the IIS VS or WS. Ensure stsfltr is the top priority, or if possible is the only ISAPI filter there. Take a look and see if that is the case. What Service Pack for WSS are you using?
Also as Thomas mentioned ensure on ALL Desktops that the WEBCLIENT service is running, and reboot the machine. Stopping and then restarting the WEBCLIENT service with out the reboot breaks it. Try from the server itself where Sharepoint is installed, again making sure the WEBCLIENT service is renabled and running. See if from the server itself the problem occurs. Also, is the site you are connecting to running on port 80, or using SSL? Another thing to note, is there a firewall or router between your client machines and the Sharepoint Server?
Later,
Jay