Removed a Taxonomy, but still shows in Admin UI

I have been testing out the Custom Press Plugin and for the most part is pretty good. I have run into one problem however...

I have a Custom Post Type called "Campaigns"
I had a Taxonomy called "Categories". Labeled the same as the "Post" categories, but in itself my self created taxonomy.

I deleted the self made Taxonomy labeled Categories and recreated a nearly identical one but this time labeled as "Campaign_Categories" for the System Name. It works ok, but the problem I am experiencing is that the old taxonomy I was previously using still shows up in the Admin UI. So for example in the Admin menu on the left I see...

Campaigns (linked as
Add New (linked as
Campaign Categories (linked as
Campaign Categories (linked as

If I actually click on the link with "taxonomy=Categories&post_type=campaign" I just load to a page that tells me "Invalid taxonomy".

Are there still traces left in the database that didn't get removed? It's even more so of a problem for me, because I "think" this old taxonomy is interfering with some other things I am trying to achieve with another plugin "Formidable Pro" and listing the correct Taxonomy in a drop down menu.

Need help! :stuck_out_tongue: