Thanks for the ping. As they test more markers on the Y chromosome, they should be able to establish a DNA profile (haplotype) that can show with a stated level of confidence how many generations back to the most recent common ancestor.
That may be how they calculated this:
They estimate that modern humans and Neanderthals split from a common ancestor at least 370,000 years ago, and possibly 500,000 years ago, although we share 99.95 percent of our DNA.