I'm getting this error too. I'm editing a section, and it won't let me save or check in/out. It only offers save as and private edit. I clicked private edit, which changed the save as to save. I then click save and got that error.
Also, no matter how many times I delete the default section, it keeps reverting to it, and won't save my changes.
I'm working inside a portal harness in one of the sections held by the harness, after editing defaults.
Problem: I too faced the same problem. I tried adding a new validate rule in a flowaction - validation tab, done this in private edit.Got the same error "********does not exist for use by this record(Validate)"
Solution: I saved the Flow action to a branch first instead of private edit and then added the validate rule, it worked without errors.