Fixed for 3.5-beta3. We reuse the same message in a few different contexts, so it ended up as this:

The parent page specified does not exist. It may have been renamed or removed since you started editing.

That is, I didn't suggest where to modify the location because the same message can appear within the move/reorder dialogs, not just on the edit page itself.

Perfect!

Yeah, I think the hint would be a good idea. I'd probably word it conditionally, since this isn't the only reason you can get the error message. It happens more often if you don't use the autocomplete, but hit enter or click OK in the dialog with an invalid page title.

The parent page specified does not exist. It may have been renamed or removed since you started editing. Please click 'Location' to select a new parent page.

How about that?

Ah, I see. I expected it to understand that the page had been renamed, and automatically change the parent reference. But I understand about the index.

Perhaps we could solve it by adding a hint to the error message: "The page may have been renamed. You can re-assign the parent by clicking 'Location' and finding the new parent page."

I think this is working as designed, Sarah. You should be able to set the parent page to the renamed page and resubmit your edits.

The reason we use space key plus page title to identify the parent page rather than the page ID is so that you can set the parent page to one that Confluence hasn't indexed yet. Switching to use an ID-based parent page submission would mean that you couldn't choose a parent page which you added in the last minute or so. The approach we ended up with seemed like the lesser of two evils.

Please let me know what your expected behaviour would be.