I had the same problem.
Under Categories option, I don’t see any category.
Under a New Entry, in category pane, I don’t see any, but I see it under Most Used.
All my entries is marked without categories and tags, but Tags Widget is filled.
If I try, from Category Menu, add one used before, It tells me exist.
If I click in Convert categories to tags, it tells me there aren’t categories.
Writing this entry, I noticed thath phpmyadmin tell me an error writing in tmp folders trying to show me the structure of the tables.
I rebooted the VPS (i suppose restarting the mysql process is enough), and all work again.
