Has there been any new software, or new versions of old software loaded
on the computers in question?

Someone in another thread found that installing HP printer software
caused the same kind of problem. A restore of his system (using Ghost)
and a reinstallation of the HP software cured the problem.

Where I work, we had problems with McAfee's answer to Symantec's NAV
Auto-Protect feature. When the McAfee auto-protect (I forget its
actual name) was active the machine running it simply would not run
Excel files from our Novell server. Once McAfee was told to go away,
we regained Excel functionality.

Look in the Task Lists of the affected machines to see if there might
be a common process running that could be the cause.

Try turning off possible culprits in the Task List to see if you get
your speed back.

That's as far out on my limb as I can go right now.... :-)