I'm still wondering where are you trying to run that fetch and if there are countries with the right names..
You can run fetchXml using webAPI.
Here is what I got (different prefix for the country entity, but, in general, just the same query I believe):
https://<ORG ROOT>/api/data/v8.2/salesorders?fetchXml=<fetch version="1.0" output-format="xml-platform" mapping="logical" distinct="false">
<entity name="salesorder">
<attribute name="name" />
<attribute name="customerid" />
<attribute name="statuscode" />
<attribute name="totalamount" />
<attribute name="salesorderid" />
<order attribute="name" descending="false" />
<link-entity name='new_country' alias='countrybill' to='billto_country' from='new_name' link-type='outer'>
<attribute name='new_code' alias='billcountry'/>
</link-entity>
<link-entity name='new_country' alias='countryship' to='shipto_country' from='new_name' link-type='outer'>
<attribute name='new_code' alias='shipcountry'/>
</link-entity>
</entity>
</fetch>

This, actually, shows two things:
- The query should work (highlighted line)
- If there is no match, you won't see those attributes in the result (the other line)