Sort by taxonomy term name in Views?
Wow do I feel stupid today. I've done this before, but just seemed to have a brain issue.

Very simple:


Add a relationship for "Taxonomy: Terms on node". Select the country vocabulary.
In the sort criteria, select "Taxonomy term: Name" (I believe this gets added by step 1) and make sure the correct relationship choice is selected.