I'm losing structure too and don't have any tags at all :)
However, I do have multiple categories with the same 'name' but different slugs (e.g., I have "West Midlands" as both a 'region' and a 'county' in my hierarchy, with west-midlands and west-midlands-2 as the slugs.
I can see two places where the export/import is likely failing:
1) in the exported xml, <wp:category_parent> does not use the slug of the parent, but its name. e.g.
2) in the import, looks like there's a check to see if a category exists before importing it... using its name:
// If the category exists we leave it alone
if ( in_array($cat_name, $cat_names) )
However, I might be wrong on both counts :)