Hi newrkhnd, welcome to the forum.

In order to sort on a protected worksheet you must also unlock the cells you want users to be able to sort. I suggest:

1. Unprotect the sheet
2. Select the cells (or columns/rows) you want the user to be able to sort
3. Right-click -> choose 'Format Cells..'
4. On the Protection tab, un-check 'Locked', click OK
5. Re-protect the sheet (remember to allow Sort) and Save the workbook (if necessary)

You should now be able to sort while protection is active.