I know this post is rather old, but thought this might be useful to anyone with the same issue: we could quickly see that any plug-in that tingles around with permalink structure is a possible cause. In our case it was a custom post type plugin which, in combination with polylang, would return “404 error” in every static page except for the main home.
The solution was rather simple, as it only took a visit to the “permalinks” settings and refresh the selected structure. This is in fact a recommended step every time a “link-sensible” plugin is activated/deactivated.
Hope it helps, and congrats for this excellent plug-in!!