Quoting the dashboard:
Deleting a category does not delete the posts in that category. Instead, posts that were only assigned to the deleted category are set to the category <DEFAULT_CATEGORY>.
Categories can be selectively converted to tags using the category to tag converter.
Thing is: posts that were only assigned to the one or more categories that got converted into tags become "Uncategorized", instead of falling into the <DEFAULT_CATEGORY>.
I'm talking WordPress 2.3.1 here --- but reading WordPress 2.3.2 in detail it seems this is still around.