Arabian baboons and Red Sea land bridges

I ran across this paper by Bruce Winney et al., from 2004, which surveyed the mtDNA variation of hamadryas baboons (Papio hamadryas hamadryas) on the Arabian peninsula (the southwest coasts of Saudi Arabia and Yemen), with the intention of figuring out when and how they got there.

For instance, were they brought over by humans recently or have they been there a long time?

The hamadryas baboon, Papio hamadryas hamadryas, is
found in both East Africa and the Arabian Peninsula (Fig. 1) and is the only species of nonhuman primate found in the wild in Arabia (Harrison & Bates 1991; Biquand et al . 1992; Kingdon 1997). Morphologically and behaviourally, Arabian hamadryas baboons are very similar to African hamadryas (Kummer et al . 1985). It is not known, however, whether this phenotypic similarity is because Arabia has been colonized only in the very recent past or whether baboon populations in Arabia are older and phenotypic similarity has been maintained by stabilizing selection. Recent ancestry is quite possible as sea-levels were low enough 18 000 years ago to expose a land-bridge (Rohling et al. 1998; Siddall et al. 2003). There is also the intriguing possibility that humans may have transported hamadryas baboons between Arabia and Africa approximately 4500 years ago, as ancient Egyptians are known to have worshipped them, considering them to be incarnations of Thoth, the god responsible for weighing the souls of the dead (Kummer 1995) (Winney et al. 2004:2820).

They conclude that the mtDNA clade diversity in Arabian baboons is too great to have gotten there within the past 20,000 years, so the dispersal must have been earlier. Then there is a question of whether the dispersal came over the Strait of Bab el Mandab or the Sinai:

Kummer (1995) hypothesized that a northerly route of colonization, via Sinai, was more likely than a southerly route across the Red Sea, via the straits of Bab el Mandeb. His reasons were that the straits, although dry during glacial maxima (Rohling et al. 1998; Siddall et al. 2003), would be salt flats and therefore an effective barrier to baboon dispersal. Regardless of direction, a recent colonization by a northerly route predicts genetic similarity between populations at the northern edges of the range on either side of the Red Sea. Our analysis does not support this prediction, as Eritrean and northern Saudi Arabian samples (Al-Akhal, Taif and Baha) are genetically distinct from one another. This suggests that a southerly route, via a land bridge, is most probable. Land bridges are thought to have formed five times during the past 500 kyr at approximately 18, 130, 270, 340 and 440 kyr ago (Rohling et al. 1998; Siddall et al. 2003). Average levels of variation within clades suggests that colonization during the most recent glacial maximum 18 kyr ago is unlikely (Winney et al. 2004:2825).

Those land bridge times are what create such a problem for the "southern route" Out of Africa modern human origins scenario, also.