Custom permalink style: “/blog/[category]/[post]/”

I’m trying to get my permalinks to work so that categories are located at “/[category]/” and posts at “/blog/[category]/[post]/”, resembling a logical directory layout. (I have a static homepage set, which is why it’s under a “/blog/” pseudo-directory.) However, I tried to set this up in the settings, but it doesn’t work. I can view a category, but clicking on the title of any post brings me to a 404 page.

How can I accomplish this?