Having a similar problem. The first two pages of posts worked fine, but then pages 3 and 4 got a 404 error.
I switched to default and it was working. So I switched back to the theme I was using (Arthemia free) and started messing around to see if I could find the problem.
Resetting the permalinks didn't help. Deactivating plugins didn't help. When I went into Settings>Reading and changed the number of posts to show on the page - it fixed it. If I put 10 as the number of posts I want to see, I get the 404 error. If I put 5 or 8 or whatever else, I don't. The theme now only shows 5 posts per page, no matter what number I put in there, but at least the pages are no longer giving 404 errors.
Any thoughts on why this could be happening? Seems to have just started up randomly. I didn't make any changes to the theme recently.