Appears that he has 188590 rows. It definitely sounds like a configuration issue. Maybe the mysql table cache might be bogged down or the query cache is full or malfunctioning. Could be a lot of things.

Sorting that into a temp table, and caching that in memory would be really fast on a server with reasonable RAM and proper indexes.