Woocommerce Plugin and Mailchimp can’t connect

I have been trying to get the Mailchimp for WooCommerce Plugin to talk to Mailchimp for the last few days on a website I am working on.

On the WordPress side it doesn’t seem to do anything – but when I look in the logs I am getting messages like:
2019-02-19T23:02:08+00:00 NOTICE api.add_product.error :: Resource Not Found :: The requested resource could not be found.

When I look in mailchimp at the API Calls I am getting “The requested resource could not be found.” messages against any POST or GET against ecommerce/stores.

There are no connected sites, and I have ensured that the server requirements have been met.

I have removed the plugin, cleared cache and re-installed many times (also tried deactivating the Cache plugin).

I’m completely stuck as to what to try next. This seems to be a recurring problem in the forum – but I can’t find a solution that I can use here.

Any guidance would be appreciated.