It should be in core-nextprev.php file and it seams it does not pass to next_post_link function the category to look for…
in my site for exemple here
http://www.canilediarzignano.it/category/adottati/page/2/
you see that previous page refer to one category, next page to another…
Thank you
