Ok,
Now this is particularly very odd…I found this forum post: http://wordpress.org/support/topic/error-404-on-pagination-when-changing-posts_per_page-on-query_posts
Which basically says that if you are restricting the number of posts to a number less than 10 (which is the WordPress default), sometimes it can break pagination. To fix this issue, all you have to do is set the default number to be less than 10, and that’ll fix the pagination. That sounded odd to me, but I set my default number of posts per page to be 1 and presto, my pagination was fixed!
This fixes my issue, but I have no idea why, has anyone else run across this issue or know why WordPress breaks the pagination in this situation?
EDIT: After taking a look around, it seems as though your number of posts has to be larger than the WordPress default. For example, on my test blog I have 8 posts, so if I change the limit to 9 the pagination will still be broken…but if I change it to one, it works just fine, because I definitely have more than one post – this happens regardless of how may posts_per_page I set on my query. So odd…anyone know why this happens?
Thanks,
Josh