I seldom have sort problems with views, but I have to admit it's not something I ever really focused on. Here's a short list of things you might wish to check. If that doesn't solve, it would be great if you could provide some more detail on your settings and what appears to be the default sorting in your current configuration.
How did you set the sort criteria in the views UI? You have basic settings available there (top right of the UI panel). See below for some screenshots that should help you finding your way around the configuration.
How did you set your taxonomy term order (accessible from somewhere similar to: http://example.com/admin/content/taxonomy/3 - where the number is the taxonomy ID).
Here is some more information on sorting capabilities of views.
Screenshots on how to configure sorting
NOTE: In this example I show how to sort nodes according to whether they are published or not, but the procedure applies equally for taxonomy terms.
In this view I already set up some sorting, add yours by clicking on the + button
Select what kind of content you want to sort
Select the information you want your content to be sorted by
And finally select the direction of sorting!
Now you should be good to go! :) Hope this helps!