I recently came across an error in wordpress where a post was visible in the admin area, and published, but when you clicked "view post" it just gave a page not found error. A quick search on Google found the following article, which may be useful to you but DID NOT solve my problem: http://wordpress.org/support/topic/page-not-found-but-exists-fine-in-admin
I eventually found the issue was "special characters" being used in the permalink. My content contributors and editor all work in word, and then copy-paste their article into the post submission form. While the editor knows to look out for special characters and fix them, the permalink had already been generated using the original title supplied by the contributor, and that title contained one of Microsoft Word's "special" apostrophes. Hard to see when you aren't looking.
Next time you're tearing your hair out over this issue, ensure that your permalinks contain URL friendly characters. I restrict mine to alphanumeric and hyphens only.
