Unable to get the sort feature to work from the header on a protected worbook (Excel 2010)

I have an Excel 2010 file that we will be sending out to 50 users and we need them to be able to enter data in some cells and not in others within the same table. That alone works fine by protecting the sheet. The catch is that we also need them to be able to sort and filter. We did the allow users to edit range trick and checked the “Auto Filter” and “sort” when protecting and it does work, but it only allows the user to sort by right clicking and sorting the used range and not simply by using the drop down and selecting sort A-Z (see screen shots below) and sorting the entire table. It’s fine if that’s just the way it has to be, but it’s not very user-friendly. I’ve attached a sample of the file (with fake data) so you can see what I mean. The blue cells are ones we want people to be able to edit and the other cells will have data we supply in them. The sheet is protected and there is no password (just hit enter).