WordPress MU

Wordpress 1.3.3 (Started with 1.2, upgraded to 1.3, upgraded to 1.3.3 today).
Apache 2 / MySQL 4 / PHP 5

One user (Editor level) is having problems when he tries to Add a category via the sidebar on the "Write a Post Page". He gets an error: Something strange happened. Try refreshing the page. (Screenshot: http://blogs.macobserver.com/error.jpg ) Refreshing doesn't help.

I (an Admin) have no problem adding categories this way.

In the error log:
WordPress database error: [Table 'tmo_blogs.wp_4_categories' doesn't exist]
UPDATE wp_4_categories SET cat_ID = '28' WHERE cat_ID = '3690'

Took a look at the SQL tables:
Indeed, there is no such wp_4_categories table, but there is a wp_4_terms table where the categories seem to be stored. I do see rows such as:
term_id, name, slug, term_group
20, blank, (random 4 digits i.e 2129), 0
21, blank, i.e 3944, 0
etc

Any idea what's going on here... like my sql or my php being out of sync (I clicked the Update link in the admin interface, and it said was successful), but why does it work for me and not this person?

Is his user_id 4? I know when you delete a user, some tables are leftover (terms, term_taxonomy, and term_relationships) which i'm thinking should be fixed soon, so either your user is missing his categories table (if that user_id matches) or the user_id pulled for that query is wrong for some reason. Me smells bug in latest release?

I have this same issue and am tearing my hair out trying to find the cause. Anyone have any ideas? I've got about 55 blogs and none of them have categories tables and the Manage Categories page is throwing db errors just like the one above.