I would assume in some cases 1000 years isn’t much of a stretch. My great grandma says she has records tracing our family back over 600 years, but I haven’t seen them personally.
What I’m wondering is, what families records go back the farthest, and how far back do they go? Is there anyone alive who can point to a name carved in ancient stone, and legitimately claim to know they are descended from them?
Well, there’s the Japanese Imperial Family.
The Japanese imperial family is the oldest hereditary monarchy today, so they would have to be contenders. They claim a lineage back to the emperor Jimmu in 660 BC, but that is suspect. For one thing, in the late second century the line is supposed to pass through a prince named Yamato Takeru, but he is more of a legendary figure and not known to have been a definitive historical personage. I am certain there are other links in that chain where scholars are sceptical of the continuity.
How far back it can be traced with relative certainty is a question someone else will have to answer.
But if you are willing to accept instances where a family counts people as ancestors in records and you do not require that they actually be blood relatives, then the Japanese imperial family is going to be one of your top candidates for farthest back, even if you stop at Yamato Takeru.
Edited to add: What Darryl said.
The longest documented ancestry is that of Kung Fu-Tse (Confucius) and his descendants. Short note on it in Wikipedia.
Several Irish lineages, notably the O’Neills, trace back through Irish legend to Milesius. There is of course no documentation for them, but longstanding oral history which, as of the last I saw it, Burke’s Peerage accepts as valid.
In Europe, the earliest documented ancestries go back to Syagrius; the note about the abbot being the last known descendant refers to the male line, and a female descendant was an ancestress of Charlemagne, and through him of much of Europeans and Americans of European ancestry.
Some Hebrews can trace back to the original ten tribes.
You’d have to define ‘traceable’, but I just watched a fascinating Nat Geo documentary on human DNA, migration and evolution.
One conclusion - the San Bushmen of Southern Africa split (genetically) from the rest of the human race the longest ago (about 70,000 years ago).
Of course they’re still human, just like the rest of us. But that’s the oldest split (from genetic markers), AFAIK, that anyone can discern.
So I imagine they get the medal for oldest traceable ancestors 
One thing to recall is just how many ancestors you have even though the line doesn’t keep doubling as you go back due to distant cousins marrying. Personally on one line, I’ve traced my ancestry back to Charlemagne. That might sound like bragging, but it’s not too hard.
If you have European ancestors, once you go back far enough, you have enough ancestors that one of them (if you can find him or her) is likely to be a noble someplace, and if you don’t find one of those, you’re generally going to be stuck to go back further. Almost inevitably that will link you into some royal line. Once you’re linked into a royal line, you usually link into many European royal lines and can go back as far as anyone else in those line. Of course, most of your ancestors remain unknown to you.
Of course, there’s always the danger of illegitimacy making all your beyond them wrong.