I am running CB 2.0.x. The example that WORKS is the site running CB 1.9.1. The site I'm trying to fix right now (802eyecare.com) is running CB 2.0.4 on Joomla 3.3.6. Although you're right that my CB 1.9.1 site has CB Core Redirect installed (I did not realize that).
I finally figured it out. You mentioned that the CB Core Redirect functionality is built into CB 2.0 now. But it's not fully _enabled_ by default. I had to go into the CB System Plugin and turn on "Rewrite URLs" (not just "Redirect URLs").