Slow queries after WP 3.1.1 update

After update to WP 3.1.1 in our most important project running wordpress, we are facing serious problems with MySQL slow queries that are causing our site going down frequently.

Slow queries look like this one:

# Query_time: 66.859010  Lock_time: 13.069493 Rows_sent: 0  Rows_examined: 252242583
SET timestamp=1303739202;
SELECT SQL_CALC_FOUND_ROWS  wp_posts.* FROM wp_posts  INNER JOIN wp_term_relationships ON (wp_posts.ID = wp_term_relationships.object_id) WHERE 1=1  AND ( wp_term_relationships.term_taxonomy_id IN (92) AND wp_posts.ID IN (
					SELECT object_id
					FROM wp_term_relationships
					WHERE term_taxonomy_id IN (77)
					GROUP BY object_id HAVING COUNT(object_id) = 1
				) ) AND wp_posts.post_type = 'post' AND (wp_posts.post_status = 'publish') GROUP BY wp_posts.ID ORDER BY wp_posts.post_date DESC LIMIT 1190, 10;

I disabled and enabled plugins with no clue, and also tried to use Theme-Check to verify possible code incompatility but we are getting a blank page running plugin.

This WP install runs on a dedicated box plenty of resources and right now our site is complete off.

What could be happening? Could anyone help us?

Thanks in advance!