In reply to.
Had a quick look at the plugin’s source and, interestingly, it does include an uninstall script, which I think WordPress registers before anything is deleted, so it can be run afterward. (Looks like it would try and delete—some?—plugin options.)
That said, (simply) enabling categories for pages literally takes one line of code: `register_taxonomy_for_object_type( 'category', 'page' );`. Of course if you wanted different categories (i.e., not the same set of categories “posts” use), that’d be a couple lines more. (I mean, I’m not sure what to think of a plugin that wouldn’t use built-in functionality like this and instead do something else entirely.)