Ok things are getting better
The rate at which you are getting complaints isn't too bad. Some of it may be attributed to just having complained for so long but we don't want to rely on that.
If it is the same (more or less) users complaining find out if it a specific application that they are complaining about. If it is find how\where it is installed and where it is getting it's data from. What you are looking for here are any ties to the samba server, the old roaming profiles, proper WINS and DNS settings etc. Also check the NIC on their machines and make sure it is running 100Mbps and preferably full duplex. If it is set to auto change it to 100Mbps.
Start with that and see what you find.
John