Could Bush issue an Executive Order making Shwartznegger a Natural Born Citizen and thus eligible for the Presidency?
An EO is subordinate to the Constitution. Short of a constitutional amendment, no.
Dunno. Can an executive order reverse time and change the geographic location of Arnold’s birth from Austria to that of the U.S. states and territories?
No. “Natural Born Citizen” is defined by the constitution and will need an constitututional amendment to be changed.
“U.S. states.” I’m so unintentionally funny.
I detest people who claim as solecistic usages like this – U.S. states means "states of the nation whose name is “the United States of America” – as opposed to, e.g., “states of the nation whose name is Australia.” In that sense, there’s nothing solecistic about the usage.
I don’t think an EO can even make someone a naturalized citizen. I believe that requires an Act of Congress.
Congress has by law clarified several instances in which a person not born on U.S. soil is still a “natural-born citizen” – a person born abroad to US parents, for example – but it’s unlikely that even a Congressional act purporting to establish Mr. Schwarzenegger as a nautral-born citizen would survive challenge.
I don’t see any authority whatsoever for the executive to take such an action.
So - no.
Actually, Natural Born Citizen is not defined in the Constitution. In Art II, Sec 2, Clause 5, the framers simply recognize two classes eligible for the Presidency: “natural born citizens” and those who were “Citizen . . at the time of the Adoption of this Constitution.” The Clause offers no more guidance on who makes up these two classes.
Subsequently, Congress has used implicit authorities to define citizenship (e.g. the Constituion grants authority to Congress to “establish a uniform rule of naturalization) to clarify the “natural born” status of certain classes of citizens. But the Courts have never explicitly ruled on the Constitutionality of any legislative definition of what it means to be “natural born”.
Sooooo*…technically*, “natural born” could be interpreted as being “vaginally-delivered,” as opposed to Caesarian. Hmmmmmmmmmm…time to place a call to Arnold’s mother. 
Does “natural born” rule out one born by in vitro fertilization? 
Actually, the Constitution also has an additional provision as citizenship: Persons born or naturalized in the United States are citizens (XIV Amendment). So birth IN the US clearly confers natural citizenship (and laws and territorial treaties define what’s “in the US”). Anything else is subject to the law, but it’s a well-accepted legal principle (jus sanguinis, by right of the blood), that the children of jus solis citizens are also citizens.
But nothwitstanding that, the answer is NO, an Executive Order cannot declare someone a “natural born citizen” contrary to the law. It can’t even declare someone a naturalized citizen, the rules of naturalization are unambiguously the bailiwick of Congress.
Article 1, Section 8, Clause 4 of the Constitution states:
“The Congress shall have Power * * * To establish an uniform
Rule of Naturalization, and uniform Laws on the subject of Bankruptcies
throughout the United States.”