When using the custom permalink setup as so: /%category%/%postname%/
Search Everything, version: 4.7.8 is causing problems. This happens when trying to view the full post, giving a 404 instead of the post itself.
I spent quite some time in the forums trying to find the cause of this problem and have seen quite a few others who have a similar problem too (though not sure if they are all related or not.)
Anyway, as a last resort, after nothing I could find worked, I decided to deactivate all plugins and then one by one reactivate and test each one, in turn allowing me to weed out any possible cause.
And it was Search Everything
At this point I am using 2.7 but, could of been happening before since I hadn't posted anything for quite sometime so 2.6 could also have this issue.
Please let me know if you need any more specifics to help with this issue.