thydzikI was cleaning up my WordPress taxonomy, manually removing tags which shared the same category name. When I then performed a tag clean up with wp-cleanup, I noticed that all my categories had also disappeared.
As tags and categories share the same wp_term_taxonomy database, I think there is a check missing in wp-cleanup to make sure any tags are not used as a category.
