In views formatted as table, columns with taxonomy term fields are sorted according to term ID, not label
That's because the stored value of the field is the term ID, the label of it is just how it is displayed.

To sort on the name, you need to instead add a relationship using that field to terms, and then add the name field of that relationship. Then you should be able to sort it as well based on that.