Strange permalink issue

Hi,
I’m using latest WP and I have permalinks like:
/%category%/%postname%/

Now each time when I edit or create a new page, I get “not found” for that page.
Then I have to go to permalinks, switch it back to default save it and then go again to enter custom permalinks and only after that I can see my page !??

There is no server issues (no error_log file) so I’m just puzzled why is this and WHAT IS HAPPENING ?

Thanks for help !