Andrew,
I would be very suspicious of that much memory for sort. Please see the docs for what that does. That is the amount that _each sort_ can allocate before spilling to disk. If some set of your users are causing complicated queries with, say, four sorts apiece, then each user is potentially allocating 4x that much memory. That's going to wreak havoc on your disk buffers (which are tricky to monitor on most systems, and impossible on some).
Yes, we have effectively complicated queries. That's why we put the sort_mem so high. I'll see if we can put it lower for the next few days to see if it improves our performances.
Thanks for your help. -- Guillaume