The first step is to find the bottleneck. If you don't already have sar running then do that. If you have the sysstat package then you have sar. You can tell if sar is running by checking for sar data files in the /var/log/sysstat directory. Once sar is running for a few hours you can see the resource usage.
Code:
$ ls /var/log/sysstat
sa10 sa12 sa14 sa16 sa18 sar10 sar12 sar14 sar16
sa11 sa13 sa15 sa17 sar09 sar11 sar13 sar15 sar17
At the same time you can check the system messages file for signs of trouble such as authorization failures or connection timeouts.
Ubuntu has an interactive system monitor as well. You can have that running all the time, then when someone complains you can check the system monitor to see if resource usage has peaked.
Poor network performance can be caused by things that are not part of the Ubuntu server. A bad router or a client with a bad broadcast mask or a bad subnet mask can cause the network to saturate with noise. A network card that is failing can cause lots of problems.
I would try to look at all of these possibilities, ruling each one out methodically.
