Blog Pagination Broken with 4.3. 404 Not Found on /blog/page/2/

I didn’t see another post about this, but if there is one please redirect me. Thank you.

After updating to 4.3 pagination on the blog of our site has broken.

Visiting /blog/page/2/ returns a 404.

My theme is just using the if have_posts() while have_posts() loop. But I have ruled out the theme by trying the twenty-fifteen theme and the 404 persisted. The only thing that has worked so far is returning to standard permalink.. but we’d like to keep our custom structure.

Here is what I’ve tried so far:

• Switching to a different theme. I tried the twenty-fifteen theme and the error persisted
• Deactivating plugins, by renaming plugin folder. Error persisted
• Turning off Bulletproof Security and restoring the default htaccess file. Error persisted
• Flushing W3 caches. Error persisted

I was able to get it working by going back to default permalinks. However, we want to use /%post-name%/ and returning to this causes the 404 again.

As far as I know nothing has changed with the server, but we host with Hostgator so who knows… It seemed to be working before updating to 4.3, but maybe it had broken at some point prior to the update and I just didn’t realize.

I feel I’ve ruled out the theme, plugins, htaccess rules. I’m not sure what else to check.

Any help would be appreciated.