This is to potentially help solve many people's problems with the "next page" being broken on category pages. Numerous posts on the topic here were left unanswered, so I started a new thread with a solution. In my case it's because a page with the same name as the category existed, in the trash. Had to delete permanently. Below full details and examples.
I had a problem with the "next page" and "previous page" on categories pages in a custom permalink structure of /%category%/postname%/. For example: http://www.mywebsite.com/myjournal/how-to-fix-next-page-issue/ (and I also had the "Wp No Category Base" plugin on.
After a searching a few days, I finally found what solve the problem in MY case.... I had a PAGE in "Pages" WITH THE SAME NAME AS THE CATEGORY (for example "myjournal"). It was in the TRASH. Being in the trash still creates a problem. You have to go the the Trash folder and DELETE PERMANENTLY.
That solved the problem instantly. I hope it does for others.