Check for high resource utilization on the clients and the server. Scan all systems for malicious software. as anything recently changed on the network? Is a data backup happening while the clients are trying to use server resources? Are the clients local to the server or is the server on a remote network? Check for link saturation. Check the LAN switch port settings. Make sure that speed and duplex settings match the NIC settings of the client and server.
What other troubleshooting steps have you taken?