I had the same problem.
I looked like this:
I have Custom Post Type “Product”
and when I was trying to display single post from this Post Type I received 404 error.
I was trying different Themes but the problem was the same.
I was trying using different WordPress versions (3.8.1 and 3.7.1) – all the same.
Then I started changing settings in Custom Post Type.
Cause of the problem: Custom Post Type set to Hierarchical.
Temporary Solution: go to Fields tab of your Custom Post Type and uncheck “Page attributes” and “Hierachical”