First, a few things to straighten out:
D. M. Behar et al. 2008 say...
A more recent geographically restricted enrichment of the African maternal gene pool was shown to have occurred during the early Upper Paleolithic, when populations carrying mtDNA clades M1 and U6 arrived to north and northeast Africa from Eurasia, hardly penetrating the sub-Saharan portion of the continent, except Ethiopia.
This goes back to that very questionable proposition about the African lineages of U6 and M1 being of Eurasian origin, when there is very little evidence to support such—the issue was discussed in detail here:
Mitochondrial DNA M1 haplogroup: A Response To Ana M. Gonzalez et al. 2007 [clickable link]
M1 and U6 are far from being Eurasian-derived lineages. Preponderance of evidence suggests otherwise, as briefed in the link above.
The authors are correct in noting that KhoiSan groups are notable for bearing the deepest clades of contemporary human gene pool; they however, make it seem as though—if only subtly—that the KhoiSans hold the distinction of being "unique" in this regard, when in fact, there are several other African groups who share this distinction. To quote them:
Early studies based on mtDNA control region variation have suggested that KhoiSan divergence dates to an early stage in the history of modern human, whereas their anthropological and linguistic features show closer affinities to each other than to those of other populations in Africa. 21,22 Their distinctiveness is also supported by phylogenetic studies of the male-specific Y chromosome that indicate that the most basal branch of the Y phylogeny is now common among the KhoiSan but is rare or absent in other populations.18 — D. M. Behar et al. 2008
It is a matter of fact that the most basal clades of the Y chromosome are variably distributed across the continent, but with the highest frequencies thus far observed in parts of eastern Africa—as the case is in Sudan and Ethiopia for example, central Africa—as noticed in "pygmy" groups, and yes, in Southern Africa—as found in KhoiSans. From the standpoint of Y chromosome markers, the most basal clades constitute haplogroups like A-M91, B-M60, followed by M168 [designated as haplogroup CT elsewhere], which in the main, also hold the distinction of being quite rare or absent outside of continental Africa.
Additionally, from the citation above, the authors make a link between the basal nature of maternal markers in KhoiSan groups and that of Y chromosome markers:
Early studies based on mtDNA control region variation have suggested that KhoiSan divergence dates to an early stage in the history of modern human,...Their distinctiveness is also supported by phylogenetic studies of the male-specific Y chromosome...
...and indeed, many other papers have indicated that male-specific markers that are characterized as being 'aboriginal' to KhoiSan groups, as opposed to reflecting relatively more recent gene flow from non-KhoiSan groups, tend to be of the basal subtypes that feature considerable microsatellite STR cluster diferences from those of other African groups notable for those same 'basal branches' of Y phylogeny—indicating considerable time of separation between Khoisans and non-neighboring extra-KhoiSan groups. For example...
The paragroup E-M35* has been observed at high frequencies in both eastern (10.5%) and southern (15.2%) Africa,...
... extensive interpopulation E-M35* microsatellite diversity (fig. 2A) between Ethiopians and Khoisan indicates that eastern Africans and Khoisan have been separated for a considerable period of time, as has been suggested elsewhere (Scozzari et al. 1999; Cruciani et al. 2002; Semino et al. 2002). — Cruciani et al., 2004 
...and, from Semino et al.:
The present study reveals that (1) only the Ethiopians share with the Khoisan the deepest human Y-chromosome clades (the African-specific Groups I and II) but with a repertoire of very different haplotypes; (2) most of the Ethiopians and virtually all the Senegalese belong to Group III, whose precursor is believed to be involved in the first migration out of Africa; and (3) the Ethiopian Y chromosomes that fall into Groups VI, VIII, and IX may be explained by back migrations from Asia. The first observation confirms the ancestral affinity between the Ethiopians and the Khoisan, which has previously been suggested by both archaeological and genetic findings... — Semino et al. 2002
The remaining 37 E-M35* Y chromosomes were found mainly in Africa, with a high frequency in the Ethiopians and the Khoisan...The distribution of E-P2* appears limited to eastern African peoples. The E-M35* lineage shows its highest frequency (19.2%) in the Ethiopian Oromo but with a wider distribution range than E-P2*. Indeed, it is also found at high frequency (16.7%) in the Khoisan of South Africa (Underhill et al. 2000; Cruciani et al. 2002) (suggesting, once again, their ancient relationship with Ethiopians) and observed in southern Europe (present study). — Semino et al. 2004 
...but Semino et al. 2002 note that:
In a previous study (Passarino et al. 1998), the genetic structure of the Ethiopian population was investigated using mtDNA and some nonrecombinant Y-chromosome (NRY) markers previously studied in the Khoisan (Soodyall and Jenkins 1992; Spurdle and Jenkins 1992)... ...Although the mtDNA did not reveal a particular relationship between Ethiopians and the Khoisan, affinities were suggested by Y-chromosome analyses.
This is apparently attributable to 1) considerable time of separation, as noted, and 2) geographical structuring of markers due to localization after divergence. Hence, even though male-specific markers showed affinities between say, KhoiSan and Ethiopian samples, that were not as apparent in the mtDNA analysis mentioned, these markers too showed distribution and frequency patterns of visibly distinct [and hence polarizing] subtypes between the samples in question.
Semino et al. 2002 note:
Groups I and II are essentially restricted to Africans and appear to be the most divergent clades within the tree. They show a patchy distribution, with high frequencies among isolated hunter-gatherer groups and in some peoples of Ethiopia and Sudan...
...In particular, Group I, observed in 43.6% of the Khoisan (usually considered to be descendants of an early African population), is present in all of the Ethiopian samples...However, figure 1 shows that the Ethiopian and Khoisan samples within Group I fall into different haplotypes (haplotypes 1, 2, and 5 in Ethiopians vs. haplotypes 4, 6, and 7 in the Khoisan), in agreement with an ancient divergence from the same ancestral population, as has been suggested by microsatellite data (Scozzari et al. 1999).
Now, bearing in mind, that D. M. Behar et al. suggest that it would not be parsimonious to date the divergence of KhoiSan ancestors from a common ancestral African group later than 90,000 years bp, can a link then be made between mtDNA markers and male-specific markers in KhoiSans, in terms of basal character of phylogeny and temporal character of genealogical divergence?
Behar et al. for the most part paint a picture of a single wave of migration being the source of the 'aboriginal' KhoiSan maternal gene pool—largely of L0d and L0k markers—no later than 90,000 years bp, [and yes, to answer the question above, the authors did make a link between mtDNA markers and male-specific markers—as mentioned several notes ago]. How does one reconcile this with male-specific markers, considered to be 'aboriginal' to KhoiSan groups, assuming that this wasn't a wave of migration exclusively of females?
Well, from the standpoint of basal character of genealogical phylogeny, there seems to be a common theme of basal haplogroups both maternally and paternally, and so, no qualms there; but from a temporal standpoint, questions arise vis-a-vis any correlation between the 'aborignal' maternal gene pool and male-specific gene pool. This is in no small part due to the fact that according to many publications, the "most basal branch of Y phylogeny" thus far identified date later than the 90,000 y bp time frame cap postulated!
National Geographic's site for "The Genegraphic Project", a project which one of the authors of the present Behar et al. study—that is, Spencer Wells—is a part of, for instance dates the MRCA of haplogroup A-M91 to ca. 55,000 years ago, while B-M60 is dated to ca. 50,000-60,000 years ago. From examination of various publications, the 'average' date given to early successful Out of Africa migrations of anatomically modern humans is ca. 60,000 years ago more or less. Naturally, this would imply that the just mentioned basal haplogroups would have to be older than that OOA date, but still, no work to date that comes to mind, has dated them either earlier than or contemporaneous to ca. 90,000 years bp.
Where does this lead us to? Is it possible then, to assume that the "aboriginal" male-specific gene pool—which was supposed to have been a part of the wave of migration that begat mtDNA markers L0d and L0k—was "erased" by a subsequent wave of migration, which would have likely been male-biased [for if it were not, one would expect some noticeable impact of the co-migration maternal gene pool]? If so, the question becomes when and why.
Furthermore, characteristic Khoisan gene pool extends well to the E-M35* Y chromosome marker, as noted before, and to reiterate...
Indeed, it is also found at high frequency (16.7%) in the Khoisan of South Africa (Underhill et al. 2000; Cruciani et al. 2002) (suggesting, once again, their ancient relationship with Ethiopians) and observed in southern Europe (present study). — Semino et al. 2004 
In descending order, courtesy Semino et al. 2004…
Ethiopian (Oromo) - E-M35* = 19.2%, KhoiSan (South Africa) - E-M35* = 16.7%, Ethiopian (Amhara) - E-M35* = 10.4%, Berber (North-Central Morocco) - E-M35* = 7.9%, Berber (Southern Morocco) - E-M35* = 7.5%, Senegalese - E-M35* = 5%, Tunisian - E-M35* = 3.4%, Algerian - E-M35* = 3.1%, Arab (Morocco) - E-M35* = 2.3% , Burkina Faso -E-M35* = .9%
Group III is less frequent in the Khoisan (28.2%), who share with Ethiopians only the M35 haplotype 19 (10.3%). Conversely, the M2 component, which occurs at a frequency of 17.9% in the Khoisan, is virtually absent in the Ethiopians. — Semino et al. 2002
Indeed; consider the fact that E3-P2* is notably rare or absent in KhoiSan groups. The significance of this, is obviously the fact that E3* is a precursor to Pn2 derived clades of E3b [including E-M35] and E3a. Additionally, it is an indicator of yet another subsequent wave of migration likely to be dated later than the 90,000 y bp time cap. However, since Bantu-speakers who live near KhoiSan groups have little to rare E-M35 distribution, in contrast to the considerably high KhoiSan frequencies, it is a hard sell to imagine that these were introduced to them by Bantu-speaking groups.
It is of interest, that Semino et al. 2002 note that...
Although intermediary Bantu-speaking populations currently separate these two groups geographically, archaeological findings suggest that the Khoisan territory once extended above the equator, to present-day southern Ethiopia and Sudan (Nurse et al. 1985, p. 105)...
This would make sense, given the distribution of the most basal branches of Y phylogeny in these regions, which is a characteristic feature of KhoiSan gene pool. However, to reiterate; E3* is rare to absent in KhoiSans, and yet, E-M35* is considerably higher amongst them than most other groups outside of sub-Saharan east Africa, including east African Bantu-speaking populations. E3* is notably present, if not in relatively higher frequencies than elsewhere, in those very same regions that carry the most basal branches of Y phylogeny as the KhoiSans do. This is an interesting contrast between east African and south African groups which predominantly carry these basal branches, aside from the fact that the subtypes of the KhoiSan basal branches largely differ from those in east Africa. It would seem to argue against the idea of haplogroups A and B markers arriving in southern Africa in the same wave of migrations as E-M35* markers [such a prospect would also tend to lower the range of the migration time frame], but yet, each wave of migration in question date later than the 90,000 y bp time cap that is supposed to mark the lower bound of the localization process of "aboriginal" KhoiSan mtDNA markers like L0d and L0k. Then again, perhaps a tenuous [and very tenuous at that, since non-E3* (P2) "Group III" markers are rare to absent in KhoiSan groups of southern Africa] assumption can be that small frequencies of E3* may have been available in KhoiSan groups, but have largely since been drifted out by neutral random genetic drift, while the E3*-Pn2 derived clades of E-M35* were subjected to positive random genetic drift, thereby inflating E-M35* frequency. This only goes to show the considerable complexity that underlies demographic events over time across huge chunks of landmass, which cannot be explained away with simple migration theories!
On a side note, can archeology clue us in on the temporal and spatial dispersion of the KhoiSans immediate ancestors?
Whether tenuously or not so tenuously, certain rock art have been attributed to San hunter-gatherer groups of southern African, like the following for instance...
Game Pass Shelter
Courtesy of the Rock Art Research Institute, University of the Witwatersrand, South Africa
RSA GAM 95
A line drawing illustrating figures as they appear on the so-called Rosetta Stone.
Side note: Essentially a simplified repro of the above rock art. Notice the slender body plan animation of the human figures, but more interestingly perhaps—in so far as it relates to KhoiSans—the human figure following the first one on the far left "herding" the cow; the figure appears to be bending, but it seems to have steatopygia—a fairly common feature amongst KhoiSan groups, particularly more pronounced in the females.
Some undated "San" paintings - Eastern Cape
Image courtesy of Geoffrey Blundell
If art can be accurately tied to contemporary groups like KhoiSan s, especially those which are very conservative in their lifestyles over a great dea l of time, and if ancient artwork can be accurately dated, perhaps it can aid us—amongs t other disciplines—in reconstructing demographic events with a reasonable level of precision!
—D.M. Behar et al. 2008, The Dawn of Human Matrilineal Diversity
—, Semino et al. 2004, Origin, Diffusion, and Differentiation of Y-Chromosome Haplogroups E and J: Inferences on the Neolithization of Europe and Later Migratory Events in the Mediterranean Area
—, Cruciani et al. 2004, Phylogeographic Analysis of Haplogroup E3b (E-M215) Y Chromosomes Reveals Multiple Migratory Events Within and Out Of Africa
—Semino et al. 2002, Ethiopians and Khoisan Share the Deepest Clades of the Human Y-Chromosome Phylogeny