Top menu category not linking to page?

First off, can't give a live link because the site is PW protected... but here's the issue.
We made a category jewelry, we assigned products to that category.
if you go into Admin catalog / categories, you'll see all the jewelry products.
The jewelry menu button appears in the top menu as expected, but if you click it, it says category not found!
If you look at the source it show the link jewelry button link as /jewelry-test
This was a category long since deleted. We've cleaned our the cache renamed everything...
any ideas?

Lasa2

If you disable the seo urls, does the link work?

It defiantly has something to do with that... it was picking up the old keyword generated by the SEO pack and making seo friendly link...tanks!