This is quite an understatement.
So in your hypothetical scenario....this hypothetical player would know that the only country Canada has a land border with is the USA, but not know what the USA looks like so as to be able to solve this without first guessing Canada?
This seems improbable to me. Chances are that if someone knows enough about a country that it's a 'single neighbor' country, or that it has a 'single neighbor' country, they will also know what the country looks like.
For example, if someone instantly knows that if they typed in Haiti it must then be the Dominican Republic, chances are very high that they wouldn't have typed Haiti because they also know what the Dominican Republic looks like. Much like chances are high that if someone knows that Canada only borders the USA, they also wouldn't have typed Canada in the first place, but would have guessed USA right away.
I think the "right" way to display the distance would be from the closest points in the guessed and target territories. So United States and Canada, sharing a border, would be "0 km", while Canada and Mexico would be whatever the shortest path from border to border would be (like 2,000km?)
I have a feeling that's a bit more difficult than centers, though. But it wouldn't be a problem as far as outlying territories go; the image is of a contiguous landmass, not the entire country.