Thanks for the input, bc. I think you're right. I'd tried adding higher priority to my rule, and it broke all the archives.
I finally got it to work by appending the CPT to the end of the category rewrite.
The only drawback here is now, within the categories, the post type must be identified by name rather than slug. Some of them have custom slugs - ice_cream may have the slug delicious_frozen_goodness, for example. (Personally not too happy about this, it was a cosmetic change requested halfway into the project.) The archive for the CPT will be accessed directly
But the archive for the category/CPT combo needs to be accessed as
Any thoughts on the rewrite there? I'm guessing it's something extremely obvious that I'm missing.
I'm also experiencing a few ancillary issues now, including the global conditional statements not always working. For example, is_front_page(), is_home(), is_single(), etc aren't operating as expected. I'm going to venture a guess that this is because of previous code I still have active that muddied up the system, so a code clean-up is in order.