Yes, have reset permalinks structure, then done so after disabling all plugins, then done so after disabling the custom theme.
Hey, thanks for your reply. Unfortunately the archives in question are behind a paywall.
The links look like this though:
http://website.com/videocategories/category/
http://website.com/videocategories/category/page/2/
The first link always works fine regardless of the category, whereas when we get to page 2 we always get a 404 error.
