Custom Post Types and Category Navigation

I am writing a plugin that is using custom post types. These post types have categories. And they use a nice permalink structure, based on the categories each custom post type is in. This works well. I can search for them, view them, etc.

The problem is that none of the category based navigation works. Clicking any category based line, generates a 404 page. But if I turn OFF the plugin that generates the custom post types, then the category navigation starts to work again. I don’t see a way to differentiate this, but sure there is? Any pointers?