No, it isn't. That means that the Canal Zone was US-controlled, but not part of the US. It was still sovereign Panamanian territory. Which is why the vast number of Panamanians living in the Canal Zone didn't get American citizenship when born."That's different from being born on foreign soil," McCain said of his own situation, noting that the Panama Canal was an unorganized territory of the United States for much of the 20th century.
The same goes for the Coco Solo military base within the Canal Zone, where McCain was born. An overseas US military installation is NOT US territory. The land is leased from the host country, and is still the territory of the host country.
For the definitive answer on military bases and citizenship:
http://www.state.gov/documents/organization/86755.pdf [PDF]
One could also argue that McCain does not meet the other popular definition of "Natural Born Citizen", "A US citizen at the moment of birth." Under the rules at the time he was born a US national (that is, subject to US law and control) but not a US citizen (no right to vote, etc.) Congress changed the rules 11 months after he was born, giving him citizenship."c. Birth on U.S. Military Base Outside of the United States or Birth on U.S. Embassy or Consulate Premises Abroad:
(1) Despite widespread popular belief, U.S. military installations abroad and U.S. diplomatic or consular facilities abroad are not part of the United States within the meaning of the 14th Amendment. A child born on the premises of such a facility is not born in the United States and does not acquire U.S. citizenship by reason of birth.
(2) The status of diplomatic and consular premises arises from the rules of law relating to immunity from the prescriptive and enforcement jurisdiction of the receiving State; the premises are not part of the territory of the United States of America. (See Restatement (Third) of Foreign Relations Law, Vol. 1, Sec. 466, Comment a and c (1987). See also, Persinger v. Iran, 729 F.2d 835 (D.C. Cir. 1984). "
Congress wisely granted an exemption to McCain - through a unanimous but non-binding Senate resolution sponsored by Hillary Clinton and Obama - so that he could run. (Had McCain won the election, the far right would be writing birther articles about McCain instead.)
Having said all that, McCain is correct that Cruz's eligibility is an open question. One of the two common definitions for "Natural Born Citizen" is "born on American soil." The issue is unresolved, and will remain so until the Supreme Court rules on it.
That definition isn't some birther-style rationalization with no legal backing: Black's Law Dictionary - the most widely used law dictionary in the United States - defines "Natural Born Citizen" as "A person born within the jurisdiction of a national government". Cruz was born outside of US jurisdiction, so he does not meet that definition.
And that's how the law is currently applied. Anyone born in Puerto Rico is a U.S. citizen at the moment of birth. But since Puerto Rico is not U.S. soil, those US citizens are not "natural born" US citizens and are not eligible to serve as U.S. president.
The bottom line: Cruz would probably get an exemption from Congress like McCain did (rather than tackle the Puerto Rico issue), and the Democrats would probably be overjoyed to go along with it.