I think there is a limitation with Sorting “Categorized Column” using picklist. In order to solve this problem you can create multiple views with the column to sort as the first column in each view and call the view based on users request[i have different buttons to call these different views]
i.e If i have a original view with 3 columns. Account No , Account Name and Account Description. I create 3 views with these column as first in 3 views and have 3 buttons to call these 3 views.
Hope its helpful. There could be better way to do it. This is just a work around.