WordPress 2.3 makes some significant changes to the way categories are stored, while updating some of my (and other people’s) plugins I found the following terms should be replaced:

$wpdb->categories is replaced by $wpdb->terms
$wpdb->post2cat is replaced by $wpdb->term_relationships
$wpdb->post2cat.post_id is replaced by $wpdb->term_relationships.object_id
$wpdb->post2cat.category_id is replaced by $wpdb->term_relationships.term_taxonomy_id
$wpdb->categories.cat_ID is replaced by $wpdb->terms.term_id

wp_terms now contains all the category (read: taxonomy) names and IDs.

wp_term_taxonomy contains the term (read category) ID, a description of what type it is (category, link_category, etc), the description and the number of posts/links in that taxonomy.

wp_term_relationships contains a lookup of an object_id (read: post ID, link ID, etc) and a term taxonomy ID (from the term_taxonomy table, which relates back to the category).

Partly this is to remind me, partly for anyone else who wants to know.