A moment ago, I decided to upgrade to the latest Wordpress version, I was running a bit behind on 2.2.3 :) The upgrade went quite smooth, all my plugins still work. But suddenly all my categories became empty strings. And the /category/ urls didn't work anymore either. After looking around a bit, I noticed my categories were stored in the wp_term_taxonomy table, with empty descriptions. Thankfully I had a backup and manually entered the descriptions for all of them.
At this point, their names showed up in the admin section again, but the post weren't linked to them yet, neither did the /category/ work.
A little more looking around, and I figured out to access categories.php?action=edit&cat_ID=20 for each category, where I had to enter the category name and category slug. For some reason, each category's slug was suddenly named -2-2-2-2-2-2-2-2-2-2-2-2-2, with increasing -2 per category.
After doing all that, my /category/ works again, and my posts seem to be linked again :)