If you are using custom post types and having issues with pagination, you might be running into a seemingly hard-to-solve problem that I ran into recently.
Do you have a page with the same name as your custom post type, such as a page called “products” and a custom post type called “products”? If so, you are probably seeing a 404 error when you try to use WordPress’ pagination. I thought it had something to do with query_posts, which I experimented with for hours. The solution was way easier than I anticipated – just change the page name or post type to something unique. So in this example, change the post type to “product” and leave the page as “products.” A really simple solution that is easy to overlook.
Though this isn’t a perfect solution, it does resolve the immediate problem. Unfortunately, I haven’t found a solution to the underlying problem yet. I will keep you posted on any new findings! Please let me know if you find any better solutions.