A couple of things:
When ~40 users are logged in it slows down to a crawl to the point of total unusability.
It is very dependent on what users are doing. If users are just logged in and not clicking links in their browser, it'll surely not have a problem ;) Figure out what users are doing when those things happen (Moodle logs are good for this!). Some modules are known hogs (chat comes to mind -- if it's chat, use the chat daemon).
The server stats you've posted are interesting -- but it looks like either the peak point is past (logged in too late!). I'd recommend running sysstat/sar and setting it to capture stats really often, so it has a good chance of logging the next spike.
In any case, it doesn't seem to have memory problems. It's more likely to be disk-bound, CPU bound or just having problems with MySQL getting too many persistent Apache connections. Search this forum for earlier postings of mine discussing max_clients and max_connections for a full discussion. Use TurkMMCache or PHPA to ease the load on your CPU.
Disable DB sessions & do some DB tuning, etc. Disk I/O could be what's killing you. Your kernel is good though in terms of disk IO -- are you using CFQ scheduler?