I've been searching all around. Two blogs that I've recently updated have had the categories unlinked from the posts. The categories are still in the database but all posts are linked with post_category 0 (uncategorized).
There is no way to edit all posts manually (one blog have over 1.700 posts).
This all happened after updating to wordpress 2.8.4.
Deactivating all plugins
Re-installing WP 2.8.4
Uploading the database backup
At the moment I'm going to try to downgrade to WP 2.8.3 just for the sake of it.
Any ideas what could have happened? I'm desperate here, and spent the last two hours searching the web (only found old solutions to old problems).