East Asia, apparently. Dave Schuler elaborates on the study's findings:
If you go back a thousand years or so ago, before world commerce exploded, there was more morphological diversity in dogs in East Asia than anywhere else. Whereas in the west there were a relatively small number of types and characteristics, e.g. mastiffs, coursing dogs, etc., in Asia there were all of those characteristics and more, some of which have barely filtered to the rest of the world even today. … Wherever there’s the most genetic diversity is a pretty good place to look for the place of origin.
The Dish 