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
Campaigns (linked as http://------.com/wp-admin/edit.php?post_type=campaign)
Add New (linked as http://------.com/wp-admin/post-new.php?post_type=campaign)
Campaign Categories (linked as http://-----.com/wp-admin/edit-tags.php?taxonomy=Categories&post_type=campaign)
Campaign Categories (linked as http://-----.com/wp-admin/edit-tags.php?taxonomy=Campaign_Category&post_type=campaign)

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: