I’m using WP 3.5.1 with WP e-commerce 3.8.9.5 and I have the same problem.
The default wordpress category pagination behaves weird since the ecommerce pagination is turned on. Turning off e-commerce pagination is not a really good solution because I have a lots of products.
I hope someone find a solution. We really need it…