Physicist: In a word: yes. But it’s not a problem in large populations.
The original questioner pointed out that in the age of Charlemagne (more or less when everybody’s 40-greats grandfolk were living) the world population was between 200 and 300 million, and yet 2^40 (the number of ancestors you would have with no overlap) is 1,099,511,627,776. As it happens, 1.09 trillion is bigger than 300 million (math!). That means that your average ancestor alive 1200 years ago shows up in your 40-generation-tall family tree at least around 4,000 times. That redundancy is likely to be much higher. Many of the people alive during the reign of Chuck the Great left no descendents, and while your family tree is probably wider than you might suspect, most of your ancestors probably came from only a few regions of the world. Most people will start seeing redundancy in their family tree within a dozen generations (small towns and all that). Fortunately, “redundancy” isn’t an issue as long as the genetic pool is large enough.
The biology of living things assumes that things will break and/or mess up frequently. One of the stop-gaps to keep mistakes in the genetic code from being serious is to keep two different copies around. This squares the chance of error (which is good). If one strand of DNA gets things right 90% of the time, then if you have access to two strands that gets bumped up to 99% (of the 10% the first missed, the second picks up 90%). However, if you have two identical copies, then this advantage goes away because both copies of the DNA will contain the same mistakes. That’s a why (for example) red/green colorblindness is far more common in dudes (who have 1 X chromosome) than in ladies (who have two). Don’t get too excited ladies; gentlemen still have two copies of all of the other chromosomes. Also, that 90% thing is just for ease of math; if 1 in 10 genes were errors, then life wouldn’t work.
The two copies that each of us carry around are only combined together in the germline (found in our junk), and that combination is what’s passed on. What makes the cut into the next generation is pretty random, which helps ensure genetic diversity (and is why siblings look similar, while identical twins look the same).
As long as genes have a chance to mix around, the chance of an error showing up in the same person twice is pretty low. That said, there are a lot of things that can go “wrong” so, statistically speaking, everybody‘s got at least a few switches flipped backwards. It happens. If it weren’t for mistakes, biology would be pretty boring.
An impressive, but somewhat speculative computer model, says it’s likely that we all have a common ancestor (a long-dead someone who is directly related to everyone presently living) a mere few thousand years ago. That person is very unlikely to be unique, and their genes are so watered down by now that it barely matters who/where they were. What the computer model is saying is that, given what we know about human migration and travel, a “single drop in the human genetic pool” only takes a few thousand years to diffuse to the farthest corners of the world.
So we all have some repeated ancestry, but it’s no big deal. You still have lots of ancestors with lots of genetic diversity.