It is possible that the users are using a roaming profile, without more information it’s hard to tell.
Make sure you check the network for load, traffic, errors and so on…
If the network load is to high than it will cause everything, across the network, to be slow.
Also check the network traffic, at the server and number of users logged in.
You can also take a machine, if possible, and connect it directly to the server or network switch the server is connected to and see if that makes any difference. If it does then you have a network issue with either interference, traffic or load.
Check the memory usage of the server, is there enough memory for the number of users logged in and using applications?
Check the CPU usage of the server, Is the CPU being over utilized? If it is a Virtual Machine, how is the CPU of teh host machine?