Brian, I would suggest you set up "sar", a unix tool available on all kinds of Unices, and have them write down the exact time(s) when there is a problem. Under Linux, I believe there is a "sadc" daemon which gathers the info.
You can then run sar, which gathers its stats every 15 minutes, and try to track down the problem. Sar has stats for CPU, disk, network packets among other things; so simply looking at the data samples for the affected times will tell you if there was a jump in disk, CPU, or network usage.
Aside from tcpdump, MRTG would definitely be recommended.
Another thing to check might be DNS settings on both server and clients - if the DNS is slow to respond then the server will "seem" slow. On a small internal network you can add the server to the hosts file on each client and see a small speed boost.
