Category pages not working after permalinks change

Hi there,

We recently updated our permalinks structure to use: /%postname%/ (from default)

Most of the site is fine but for some reason category pages don’t display. We have tried various url’s to show the content but none seem to work.

This doesn’t work:
https://mywebsite.co.uk/category/destinations/country/city/catID
https://mywebsite.co.uk/category/destinations/country/city/

but this does:
https://mywebsite.co.uk/tag-city/catID
& well as all pages.

If I do this it also works:
https://mywebsite.co.uk/?cat=43

Any thoughts appreciated!