I’m no expert — this is just what I found from poking around. You could try looking at each category and discerning from the posts what it should be, and then editing the wp_terms table.
I’m having the same problem — I have found that the categories are kept in the “wp_terms” table. If you have your pre-upgrade sql backup open in a text file, you should be able to edit the new wp_terms table to fix this.
In my pre-upgrade backup — the category information was kept in the “wp-categories” table. I’m just editing each line in the “wp_terms” table to update the information.
