Taxonomy sorting in view
Make sure you have Taxonomy: Term selected under the Sort Criteria box and not Taxonomy: Term ID.  

I believe the sort that you are seeing under Format -> Settings is where you can select which fields are sortable and the default sort for a view of format: Table.  Making a field sortable creates a clickable link as a header for the table column allowing you to change the sort order by that field.