Problems with permalinks can be tricky to solve because they can be caused by multiple factors. Have you tried the following suggestions?
My custom post type and/or CPT-onomy archive page is not working
If archive pages are enabled but are not working correctly, or are receiving a 404 error, it's probably the result of a rewrite or permalink error. Here are a few suggestions to get things working:
- Double check "Has Archive Page" Make sure the archive pages are enabled.
- Are pretty permalinks enabled? Archive pages will not work without pretty permalinks. Visit Settings->Permalinks and make sure anything but "Default" is selected.
- Changing rewrite rules: Whenever rewrite settings are changed, the rules need to be "flushed" to make sure everything is in working order. Flush your rewrite rules by visiting Settings->Permalinks and clicking "Save Changes".
If none of those solved your problem, can you send me a screenshot of the "Advanced Options" in the CPT-onomies settings for your custom post type?