Apparently I'm not the only one having problems with the categories after a Wordpress 2.6 upgrade.
So, time to give something back to the Wordpress community, some screenshots on how I fixed it.
First of all, I upgraded from 2.2.3 to 2.6, it's possible this solution will work for you, but I don't make any promises.
I started by going to phpMyAdmin and having a look at the wptermtaxonomy table, and noticed all the descriptions where missing.
When I took a look at the backup file I made, more specifically, the wp_categories piece, I noticed the counts and ids matched up.
I then manually edited each record, just hit the pencil icon, and filled in all my descriptions again. If you know some SQL you could do this faster, but anyway, everyone can do it manually :)
After I've done this, I visited my admin section and noticed the Descriptions were filled in again. But there was no Name, and all my posts still had empty categories linked to them.
To fix this, visit http://your-site/wp-admin/categories.php?action=edit&cat_ID=1 where 1 is the category id to edit. Fill in a Name and a Slug, the url name for your category, and save it.
Repeat this process for all your categories, until they all have a Name again.
And that's it! Categories fixed, posts linked, category urls working again.