I have 2 problems with post permalinks. I was using 3.8.1, then upgraded to 3.9-alpha-27111 and have the same problem. I could not find a reported bug that matches.
There are 2 problems with permalink structure of Post Name /%postname%/
1. Delete a page but leave it sitting in trash. Then create a post with the same name. The permalinks to the post will result in a 404 error since it is trying to link to the (trashed) page. This happened when I decided to move something from a page to a post.
2. A post with no title will have a permalink of the post ID. This will be interpreted as a year, and will result in a 404 error unless you happen to have some archives from the year matching the post ID. For example, my post with no title and ID 1806 has this result when :
Query String: year=1806&debug-this=rewrites
Actually on further investigation, if the post has a numeric title it is also interpreted as an archive year. If you create a post titled 2014 and click on a permalink to it, you get the 2014 post archive.