Custom Post Archives Not Displaying Properly

Hi, on our website we have a custom post type we use to display videos, and within these we have the ability to search archives by category, length, etc. We’ve noticed that there are problems displaying the archives for categories (and one length category) that were created after a certain point a few months ago. The first page of the archive displays, but we get a page not found error for any pages 2 and beyond. All the categories that existed before a few months ago have no problem with this, and we’ve checked our records to see if any plugins were added or changes to the theme files were made, and nothing.

I searched the forum and found people with similar problems but that affected their entire archive, not just parts. Even still, I’ve: resaved permalink settings, deactivated all plugins and the reverted to the default theme and then saved permalink settings, etc. etc. and none of that is fixing this.

Curious if anyone has a clue of where to start troubleshooting. Thanks!