Humans and Neandertals coexisted and interbred about 50,000 years ago. Mitochondrial Eve is thought to date back about 150,000 years ago. Of course, it is possible that there are as of yet undiscovered branches in the mitochondrial family, and Mitochondrial Eve dates back quite a bit further. Before the dude from South Carolina took his DNA test, Y chromosomal Adam was thought to date back about 150,000 years, but finding him pushes Adam back perhaps 250,000 years. And if some Neandertal mitochondrial lineages are found in humans, that could push Mitochondrial Eve back to more than 500,000 years or so, to before humans and Neandertals split.

There's no explanation there. If we did find Neanderthal mitochondrial dna in some human population, that would just mean mitochondrial eve would have lived longer ago than we thought (before Neanderthal and sapian lineages split.)