[jcranmer]

That is a paradox more of spherical geometry.

Dakar is about 4000 miles from the North Carolina coast. If you move the destination up the longitude of that point, you have to go 1000 miles north from the coast (in Quebec, in fact!) to get 4100 miles away from Dakar. The fact that Canada is much further north than Africa doesn't add all that much distance, but Newfoundland jutting out so far to the east reduces the distance quite spectacularly.

Over longer distances, the spherical effects are even more screwy. The shortest way to get to Mecca from Seattle is to actually start flying north along I-5, and Thule, Greenland and Minsk, Belarus are natural pitstops along this route.