Mass assigning uncategorized posts to a category

I have a large amount of posts that are not assigned to any category. I am looking for a painless way to assign these post to a category (or at least properly mark them as “Uncategorized”).

In WordPress, these posts are labeled as “Uncategorized”, but are not linked to that category. Here’s a screenshot of the Manage Posts screen with a few properly categorized posts and some that aren’t.

This is all probably due to a combination of migrations from previous WordPress installs and conversions of categories to tags.

I could not find any plugins to help me with this. Nor could I find any documentation pages or support forum posts. I’m hoping someone can help me fix this.