As far as I know, I have been exchanging only the seven regional categories (Pacific, Intermountain, Great Plains, Midwest, Southern, Mid Atlantic, and New England) for the applicable state-sub-categories, and adding state-sub-categories to pages missing them. I have tried to leave all other categories in-place.
If I deleted a "Category:Regional Programming" tag, it was by mistake. Even though I hadn't checked out that category page until just now, I was guessing it was a special-grouping that I should not change. It looks like it could be useful in a variety of ways.
Thanks for the clarification about its use, and for replacing the deleted tag,