What 1,500 years gap? There are megaliths in Israel, the Straight of Sicily and southern Portugal around 7,000 BCE, then other megaliths in southern Portugal around 6,000 BCE. During the 6th millennium BCE we see megalithic sites popping up in the Levant (Rujm el-Hiri in Israel), Egypt, Malta (
Skorba temples), Portugal, Andalusia (La Almagra), Galicia, Corsica, as well as southern, central and western France (including Poitou and Brittany). What we see is a coherent complex of megalithic cultures spanning from Israel to Portugal and to Brittany, following maritime routes along the southern and western coasts of the Mediterranean and going up to the Atlantic coast of Europe. For example, the oldest megaliths in Brittany are dated to 4,800 BCE, but other were built again around 4,000 BCE, 3,300 BCE, 2,500 BCE and 2,000 BCE. Likewise in Malta there are megaliths from 4,800 BCE, 3,600 BCE and 3,200 BCE. In southern Spain, they are dated from 5,000 BCE, 4,000 BCE, 3,500 BCE and 3,000 BCE. Obviously these people weren't building megalithic monuments every century, as they tend to last, but you can see the same pattern back and forth between Israel and Portugal and between Spain and Brittany. There seems to have been a lot of movements in both directions. It was not a simple east-west migration but more likely a trade route that was used for several millennia.
I didn't suggest that Megalithism originated with the Natufians (CT, E1b1b) but with the R1b-V88 cattle herders who came from southeastern Turkey and northern Syria. I think at first it might have been only R1b-V88 herders who colonised North Africa. If there was another haplogroup it would have been T1a, but I associate it more with goat herders. Nowadays Sub-Saharan Africans tend to have only R1b-V88 (mostly Sahel, like the Hausa, Fulani, Kirdi and Berbers) or T1a (Horn of Africa), but not both together, which suggests separate migrations. The Horn of Africa also has a lot of E1b1b, but there is too little data now to estimate how much of it is Palaeolithic (old clades like M281, V6 and V92) vs Neolithic. Interestingly G2a is not found in Sub-Saharan Africa, but only in North Africa, meaning that there were at least three distinct colonising events from the Near East during the Neolithic.