I have the permissions set under protection to allow sorting; but, But, users get this message "The cell or chart you're trying to change is on a protected sheet. To make a change, unprotect the sheet. You might be requested to enter a password."
Allow Sorting allows the user to sort unlocked cells, locked cells still cannot be moved.
It sound like your users are sorting a range that includes both locked and unlocked cells. Perhaps whole rows.
To sort while a sheet is protected all the cells in the sort must be un-locked AND the allow sorting option must be set.