Problems with extreme slow database queries in Drupal 7
When a server's I/O performance (especially its disk write performance) reaches its limit, it'll probably show first with cache queries because they're frequent and can contain some quite big chunks of serialized data.

I recommend you take a look at your disk I/O while you're waiting for a page to render, by using iotop for example.

The best way to prevent those I/O bottlenecks is to keep page requests from even reaching Drupal by putting a Varnish cache in front of the webserver. If they need to be answered by Drupal, though, at least take the cache load from the database by using Memcache.