How can I allow sorting of data while preventing changes to a header row?

I find that when, to prevent changes to the header row, I formatted that row
only as Locked and applied Protect Sheet, the Sort function does not then
work even though I check the "Allow all users of this worksheet to ... Sort"
box in the Protect Sheet options.

Excel displays a "The cell or chart you are trying to change is protected
and therefore read-only" message.

Yet if I apply Protect Sheet when the header row is not Locked format, the
Sort option does allow sorting.

Howard