Just a couple more suggestions for things to check - although this is more probably for getting to know the network better. Buds suggestions first though - especially the service packs.
1. How are IP addresses are assigned on the network? DHCP, even on a small network can be very useful and going forward using this option will make life easier.
2. How are permissions set up on the network? Individual permissions assigned to shares can very quickly become difficult to administer. Groups are much easier to keep track of.
3. Are the servers showing any errors in the event logs?
4. Are any logon scripts running? If so what do the logon scripts do?
5. Are there any unusual services running on the servers or the workstations?
6. Is there enough disk space on the Exchange server?
For the users its more likely to be a case of Do they have any problems working with the computers or the network, generally from that you can get an idea of enhancements that could be made to help the users out.