/blog/ permalink prefix causes category pages to 404

I bet you have a page named “Blog” with a slug “blog” in your system too? You can’t have that with the permalink structure you have created because the permalink for this page would also be /blog/ and therefore cause a conflict. Try changing the slug of the page “blog” to something else.