Thanks Skip:
In inspecting the columns that are protected there is no header. When I try Data | Sort - there is no header however, I might not be looking at the right thing though as per your post.
I have found a work around which is satisfactory but I would like to sort this out somehow.
As a workaround I placed the protected columns to the far right of the sheet and when sorting all columns to the left of them, they sort appropriately correctly.
I would upload a zip of the file for you to look at but I don't think it can be done at Tek-Tips