Permalinks and pagination are not working in WordPress with WP e-Commerce plugin

I’m having the same problem, though my initial product-page and categories are working fine, going to page 2 fails. Products-page give me an empty page and the categories give me unexpected, unthemed results.

The fix was to turn off ‘Use Hierarchical Product Category URL:’ in Settings/Store/General

See this thread for background.