Product Category pages display a 404 when clicked

We recently went to a paid provision with you guys after having had a few years away from the monthly subscription.

During our last stint with you, we made use of the Marketpress plugin. The store worked swimmingly however, since upgrading to the current version, we've found issues with our product pages.

As an example:
shows the main store page.

If you click on any of the product categories listed, the 404 page is displayed.

Gig Tickets is a perfect example:

I've disabled all plugins and enabled only the Marketpress plugin before testing again - the issue persists.

If I go to a known product page, for example:
Add the item to the cart and click to checkout the page appears to reload rather than take me to the checkout.

I've switched to the default Wordpress theme and experience the issue in that mode too.

.htaccess etc also look good to me.

Are you able to help please?