I think I may have narrowed down this problem.
It seems that my rewrite base is /blog/ and any post or category that has “blog” at the start of its slug just returns a WordPress 404 (not server).
I tested this by creating a new post just called “blog” and found the same behaviour.
I think this might be a WordPress bug that the developers need to investigate?