First, that the fact President Obama was allegedly a British/Kenyan citizen or Ted Cruz a Canadian citizen at birth is relevant.
Second, that the child born to US citizens who are overseas is not a natural born citizen.
Bring out the silver bullets below.
Many Americans have citizenship in a country of their ancestors according to that other country's laws and whether they want it or not. I've seen first-hand an American-born child of Israeli parents told at Israeli passport control that (1) he's Israeli in their view and (2) not only that, but eligible for conscription. In Nicholas Gage's memoir A Place for Us he relates a similar experience with Greece, which means Michael Dukakis was a Greek citizen, to Greece. Germany also grants citizenship to children born abroad. The list is probably much, much longer. And if this were true, it would save us a lot of grief if Cuba or Venezuela would declare large swaths of the Republican Party as citizens, leaving them no one eligible to run! It makes no sense that we would outsource eligibility for our presidency.
The second question is whether Calgary Cruz is eligible to be President, born in Canada to a US citizen mother. A similar question would have arisen if Barack Obama had really been born in Kenya and not Hawai‘i. The familiar citizenship decisions go the other way, so to speak: they establish citizenship for children born in USA territory to non-citizen parents (e.g., Wong Kim Ark).
The clause that requires the President to be 35 years old has an obvious meaning, but "natural born citizen" does not. The consensus is, and has been for a very long time, that it means someone who was a US citizen at birth, so he (or she) need not be naturalized. However, even by the time of independence, there were centuries of English law on the subject. All the way back in 1350, Parliament passed that [contained in WKA link above]
[A]ll children inheritors, which from henceforth shall be born without the ligeance of the king, whose fathers and mothers at the time of their birth be and shall be at the faith and ligeance of the king of England, shall have and enjoy the same benefits and advantages to have and bear the inheritance within the same ligeance, as the other inheritors aforesaid, in time to come; so always, that the mothers of such children do pass the sea by the license and wills of their husbands.'
Moreover, Parliament from time to time asserted that not only were certain persons subjects, but that they were "natural born", e.g., children born to Royalists who had fled the realm during Cromwell's Protectorate.
Moreover, the Naturalization Act of 1790 touched on the question. Certainly the first Congress's understanding of Constitutional language is critical. And it provides that children born overseas to a citizen father (no one cared about married women back then) who has resided in the United States is a natural born citizen. What Congress (and Parliament) from time-to-time regulate is just how many years the citizen parent must have lived in the USA (resp., Britain), because such citizenship does not descend through generations who do not live in home country. Cruz's mother having spent her entire childhood and early adulthood in the USA, Cruz is a citizen. Obama, interestingly, would not be, because his mother was simply too young to have met the requirement of living in the USA for five years past her sixteenth birthday. (That must explain why they got Honolulu newspapers to carry the fake birth announcement.)
Let us leave crank birtherism to the Other Team, OK?