Hi - I have a similar problem, but not quite the same.
I have a category with 41 products in it. If I view them 5 to a page I can click the next page number and the correct page appears until up to around page 6 or 7. Then it seems to lock up and whichever page number I click it stays put. If I change the number of products to view per page to, say 15, I am unable then to change it back to 5.
If I inspect an individual product the navigation arrows at the top of the page work fine. VM cookie check is turned off.
Has anyone any ideas?
Thanks - Ian