This should not happen. I think the countries should always be sorted alphabetically when the column is clicked.
Can you replicate on the demo: http://demo.piwik.org
or do you mean that the sort order (desc instead of asc) is not correct ?
Please comment with your expected behavior VS what happens, and what you think the bug is. thanks