Page Templates stop working

Oddest error.

I have page templates for all my pages and a custom sidebar that is unique to every page. It only display posts relevant to that page. Which works fine..

The problem is if I add a new category and click on it on the sidebar the page template goes away and it reverts back to the standard template. Only new categories seem to do this its almost as if the category no longer stays on the page template.

Thanks,