Can you please let me know the solution to this problem? Exactly the same thing is happening to me.
When a category in the sidebar is selected the next|prev links don't work.
The beginning of the URL is missing. It's trying to find products_results.php.....
The next|prev links work ok if the product category is selected from the top menu.