Permalink Structure for Category Template Use

Wonder if someone could help me understand something with creating custom Category Page Templates.

I looked at this:
category-slug.php
category-ID.php
category.php
archive.php
index.php

I created from my category.php file some slug templates called, category-news and a category-blog set of templates.

I set the permalink structure to:
%category%/%post_id%/%postname%

And my template shows up but then the blog post says page cannot be found.
The link looks something like this:
http://thedomainimusingforsite.com/39/blog-entry-one/
I have this on a test server so it’s not actually visible to the public.

But the second I do like what the url says above:
%post_id%/%postname%

The template defaults to the default template and the post is visible, but now obviously my custom category template is no longer being used.

I tried other variations like:
%post_id%/%postname%/%category%

Any insight would be appreciated.

Thanks,
Jonny