I was referring to the "Do you want to update links" prompt ( which is the same as UPDATE from the Edit/Links menu options, which works fine when you say "Yes". That's on a protected sheet.
No, I do not have the options for Update Links, or Change Source available with the sheet protected, but you didn't mention that before.