OK, so when I've had some food (very important), I decided to check my error_log and found this:
[30-Apr-2011 10:08:09] WordPress database error Got error 28 from storage engine for query SELECT t.*, tt.* FROM wp_terms AS t INNER JOIN wp_term_taxonomy AS tt ON tt.term_id = t.term_id INNER JOIN wp_term_relationships AS tr ON tr.term_taxonomy_id = tt.term_taxonomy_id WHERE tt.taxonomy IN ('category') AND tr.object_id IN (3467) ORDER BY t.name ASC made by require, require_once, include, get_header, locate_template, load_template, require_once, wp_head, do_action, call_user_func_array, adjacent_posts_rel_link_wp_head, adjacent_posts_rel_link, get_adjacent_post_rel_link, get_permalink, get_the_category, get_the_terms, wp_get_object_terms
A quick all-table optimize in phpMyAdmin fixed that up real quick and things are fine even after upgrading again to 3.1.2.
I can sleep now :D