Y-Chromosome Evidence of Southern Origin of the East Asian–Specific Haplogroup O3-M122:

...Our results indicate that the O3-M122 lineage is dominant in East Asian populations, with an average frequency of 44.3%. The microsatellite data show that the O3-M122 haplotypes in southern East Asia are more diverse than those in northern East Asia, suggesting a southern origin of the O3-M122 mutation. It was estimated that the early northward migration of the O3-M122 lineages in East Asia occurred ∼25,000–30,000 years ago, consistent with the fossil records of modern humans in East Asia.

Take it all with a grain of salt, in light of possible revisions in the "Standard Model" of modern human origins, but a date of 25-30,000 years BP isn't that much earlier than the coalescence points some bandy about for New World lineages.

On a related note, I added a new weblog to the blogroll that deals in East Asian genetics, Quetzalcoatl.