I too have run into this problem.

It seems strange that when a sheet is protected, and with both the sort and autofilter options checked you still cannot use the autofilter sort functionality. This seems to be caused by the fact that the cells are being rearranged during a sort event, and not simply hidden (as during a filter event).

I can't understand why this sort functionality would still be disabled despite the sort and autofilter options checked on a protected sheet. Sounds like a bug to me.

...still looking for a solution.