From what you've described, this sound like a bug to me... when you export a catalog, all the collections containing any affected photos should carry over, including sets.
Keep in mind that collections and sets will only be exported if the images being exported are in those collections/sets. IN other words, if the photos you're exporting as a catalog aren't contained in certain collections, those will not be exported to the new catalog.
But if sets are being lost, I suspect something's wrong internally, and there's probably nothing you can do about it. That said, you'll need to do some test exports using controlled factors. I'd recommend making a set of sets ;-) just for this purpose.
See if the level of nesting is making all the difference, or consider other factors too: smart collections vs. regular collections, collection names, how many photos in the collections/sets, and whether the photos exist in multiple collections/sets.
I'll be very interested to hear what you can consistently reproduce, and if it's a bug, this is a big one that should be reported to Adobe.