have/had the exact same problem.
the posts per page value in the wp backend was set to 5 and i used posts_per_page queries for my custom archive pages with 15 posts per page. as others have mentioned already the problem was that the paging gets screwed up. the paging recognizes the set value and shows me correctly the “earlier posts” links. the link itself brings me to 404 page. few tests showed me the internal value for the paging seems to be back to the default of 5.
apparrently lots of developers are struggling with that issue and i couldn’t find any proper solution online. (didn’t test any plugins though..)
my workaround is to reverse the values. so i set 15 as default value in the wp backend (for archives) and used posts_per_page 5 for my blog. luckily the paging problem didn’t occur this way…
maybe this hint might be helpful for one…
o.