Yes. DNA mutates at a steady rate each generation. The “molecular clock” is a powerful technique that is usually used to infer the time since two species diverged from a common ancestor, but could also be used to detect a time traveller from that far back - certainly if you could sequence the entire genome from a living time traveler. No single mutation would be a smoking gun, but the statistical pattern across the genome when compared to the modern human population (including polymorphisms in the modern human population) would tell you.
The article is somewhat misleading. This is based on mitochondrial DNA, which is inherited without recombination through the maternal line. In terms of mitochondrial DNA lineage, it is interesting - it shows that the mitochondrial DNA lineage of Cheddar man survives. But the fact that Cheddar Man and any given modern person are related is in itself unremarkable. If Cheddar Man is the ancestor of anyone alive today (his lineage did not die out) then it is overwhelmingly likely that he is the genealogical ancestor of everyone alive today in the UK, and quite likely that he’s an ancestor of everyone alive on earth. This is simply a function of the fact that everyone has two parents, so the number of ancestors doubles each generation as you look back (until inbreeding saturation, when two different genealogical paths trace back to the same individual).
The most recent common ancestor of all humans probably lived about 2,300 years ago. At around 5,000 years ago, you reach a point of probable identical ancestry - where every human alive today had the exact same entire set of ancestors. In other words, everyone alive at that time was either an ancestor of every modern human, or their lineage died out completely.
Rohde et al Nature 431, 562-566 (30 September 2004)
Modelling the recent common ancestry of all living humans | Nature