It was thought that the most recent common paternal ancestor of contemporary humans lived considerably later than the most recent maternal ancestor. The male lineage is inferred from Y chromosome sequences (the Y chromosome of course, is passed on only to male descendants), while the female lineage is inferred from mitochondrial DNA sequences (mitochondrial DNA is passed on only through the mother since mitochondria in the offspring come from the mother's egg and not the father's sperm). Now two reports (Poznik et al., Francalacci et al.), through sequencing of Y chromosomes from many men, suggest that the most recent common male and female ancestors lived around the same time. Wow, what a relief! Still, they are very unlikely to have directly interbred and probably lived apart in time and space. Geneticists think that you can trace the Y chromosome and mitochondrial DNA to a single man and a single woman. This does not mean that they were the only breeding humans alive by any means; the rest of the genome was recombined and passed on through many more individuals. It simply means that the non-recombining Y chromosome and mitochondrial DNA of other individuals were lost over time in the relatively small breeding populations (in other words, since on average males have only one surviving male offspring, it is easy to imagine that in most cases the Y chromosome could be lost in a given lineage, unless a specific male has a lot of male offspring, and the same with the maternal mitochondrial DNA inheritance). So it's still no comfort to literal biblicists: "Adam" and "Eve" lived apart roughly 100,000 years ago (commentary in LiveScience and Nature).
Caveat emptor, though, another report suggests an even older common male ancestor (Mendez et al.). Genealogy is messy business.