Why are my queries getting really slow?
Take a look the queries in your question

/* Execution time 7.0095062E-5 */
SELECT t.*, tt.* FROM wp_terms AS t INNER JOIN wp_term_taxonomy AS tt ON t.term_id = tt.term_id WHERE tt.taxonomy IN ('category') AND tt.count &gt; 0 ORDER BY t.name ASC

/* Execution time 5.3167343E-5 */
SELECT post_id, meta_key, meta_value FROM wp_postmeta WHERE post_id IN (77375,77379,77381)

/* Execution time 9.2029572E-5 */
SELECT wp_posts.* FROM wp_posts WHERE ID IN (77381,77379,77375)


Look at the execution time above each query


7.0095062E-5 is .000070095062 seconds
5.3167343E-5 is .000053167343 seconds
9.2029572E-5 is .000092029572 seconds


The SQL queries themselves are fast.

Please read any release notes on WordPress 3.4.1 to see if WordPress upgrade installed any DB-related modules that need tuning or deactivation. Also, check for any data that was added during the upgrade process that may have bloated your tables.