Category page for custom-taxonomy shows 404 when using custom permalink structure

Add flush_rewrite_rules(); after your register taxonomies. That fixed it for me.

Edit

Do make sure you do it on install of your plugin if you’re using it on one. It should only be run once on pug-in activation – and not on every page load. Alternatively visit Settings > Permalinks page as this flushes the rules too.