Permalinks broken due to plugin interference

Hello,

Whenever the plugin is active, if I update the theme or any another plugin my Category Archives permalinks break. For example:

URL/category redirects to [Book whose title starts with the ‘category’ word]

and

URL/category_without_match_in_any_book_title redirects to 404

The issue can be manually fixed by re-saving the permalinks structure, but this is beyond annoying and requires constant watch over any auto-update.

Can you please advise on how to fix the issue?