Page Not Found for posts I can see in the archive

I have tried disabling all plugins, reverting back to the base theme and this repros then as well.

There are posts I can see when I browse the posts. By that I mean I can see the full post on the page. When I click the post title I get a page not found error.

These posts also show up in search results and clicking the title then also results in a page not found.

The page not found is a wordpress page, not a full 404 for that URL.

Any ideas?

Thanks,
-p