are the users using roaming profiles? if so check to see how big the profiles are getting.
what type of network backbone are they on? 10/100? gigabit?
are the workstations networked on a switch or a hub?
Is the server on the same network?
If they are using windows xp check to see if they are using offline files. Go into My Computer. Go to Tools > Folder Options. Then go to the Offline Files tab. The syncrhonization of their personal files will take a while if they have a lot of files.
If you have a managed switch you can check the usage on the switch to see if there is a bottleneck there.
And run performance monitor on the server to see what is bottlenecking on it. Try to check disk I/O, Memory usage, page file usage, Rx/Tx on the NIC. This will help narrow down the issue.
#######Added by kb3cgj##########
About 90% of the times I have seen this..it was because the end users didn’t have their DNS set to the PDC and BDC. Or the DNS was mis-configured.