A recent installation of wordpress with only a few plugins was totally broken by activating the Polylang plugin. All the pretty permalinks of my pages led to 404 errors. Disabling Polylang or changing back to the default link structure solved the problem, but both Polylang and the pretty links are a must.
After some (I mean hours of) researching I found out that the flush_rules() function could be responsible for my troubles and plugins that help creating custom post types are the main suspect.
I have CCTM installed and indeed it has an option in it's Global settings to Flush permalink rules enabled by default. Unchecking it solved the problem, everything works fine now.