What’s a sample URL? I.e. which theme file is displaying your results?
There are some settings under CCTM –> Content Types –> Edit –> advanced tab… specifically the “Enable Archives” checkbox (and optionally the “Include in Search” box). However, I’ve seen some themes that set up their queries differently than others for the category pages.. so that may land you in PHP land to omit results from custom post-types…
A sample url might be http://www.example.com/blog/category/alligator/.
If it helps, we’re utilizing the roots theme. I’ve disabled all of these options as well.
From your description, it sounds like the CCTM is doing exactly what it should be doing: you tagged a page as belonging to a category, so the category page lists that page in its results.
Change your post-type settings and see if the behavior changes. Otherwise, you’ll have to edit the loop/query in your category pages to show/hide based on post-type.