Check in e.g. phpMyadmin if categories are in fact listed in the _news_cats table. If they are, then start looking into what could possibly go wrong during the upgrade. Did you follow the proper upgrade procedures e.t.c.
Make a backup of what you got before you start chopping it.