I am also having the same issue. When I click NEXT PAGE on a category with more than one page I get a 404 error.
If I use the default permalink structure it seems to work fine though but I want to use custom permalinks for SEO purposes.
UPDATE: The issue seems to only happen when I use the /%category%/%postname%/ permalink structure and works with all other permalink structures.
Anyone know a fix for this?