post_nav_links in category link to main page instead

I just upgraded from 2.1 to 2.1.3 and now post_nav_links on my category page links to the next/previous pages on the index instead.

I have a category-##.php file with

<?php posts_nav_link() ?>

outside the loop. While the links show up, they link to, for example, https://domain.com/blog/page/2 instead of https://domain.com/blog/category/name-of-category/page/2.

I am using the category_query_string plugin, but I still get the same problem if I disable it. I wonder if the problem is somehow related to permalinks, because if I set permalink structure to default, the problem goes away.