I have encountered this problem as well. We run a complex WPMU site and I haven't had a lot of time to investigate, but I believe it may be happening when there is some sort of conflict between slugs of categories that are children of other categories.
In WPMU, if you have two blogs and create a category in each with the same nicename, they will end up with the same category ID; presumably so that cross-blog queries of a category are more straightforward. For example:
Let's say we have a new WPMU install with two blogs, Blog A and Blog B, and a sitewide tags blog, Blog T.
Blog A has a category called 'Category Alpha', a slug of category-alpha, and an category ID of 1. Blog B has a category called 'Category Alpha', a slug of category-alpha, and a category ID of 1.
However, if the two categories have the same nicename but the category hierarchy (or you could call it 'path') is different, then they end up with different category IDs. For example:
Blog A has a category called 'Category Beta', a slug of category-beta, and a category ID of 2. Blog B has a parent category called 'Category Gamma' (slug: category-gamma), a child of that category called 'Category Beta' (slug: category-beta), a path of category-gamma/category-beta, and category IDs of 3 (for Gamma, since it would have been created first) and 4 (for Beta, created second).
Now, even when both Blog A and Blog B have two categories with the same name ('Category Beta') and same slug (category-beta), they have different IDs (2 versus 4) because their paths are different (category-beta vs. category-gamma/category-beta).
The problem comes in here: the plugin doesn't seem to preserve category hierarchy when copying the categories over to the sitewide tags blog, so you potentially end up with a big WP no-no: two categories on the same blog, with different IDs, but the same path. Blog A's 'Category Beta' (category ID 2) and Blog B's 'Category Beta' (category ID 4) both get imported into Blog T and both with a path of simply 'category-beta'. Uh oh.
Somewhere along the line, probably as a last-ditch effort to Stop the Universe From Exploding™, the categories' nicenames and slugs are set to their IDs (a category named '1', a slug of '1', and an ID of '1', resulting in what seem to be a bunch of 'random numbered categories.'
I could be totally off on this, but that's my hypothesis. Hopefully it wasn't too confusing. I imagine it could be solved rather easily by keeping the original category structure on the sitewide blog.