Can Ted Cruz's eligibility to run for president be tested in court? It shouldn't be too difficult. It's true that individual voters probably don't have standing to object to his candidacy; their interests are too diffuse and generalized. And Cruz can't just go to federal court for a declaratory injunction without some plausible claim that he's in danger of government action being taken against him.
But all it takes is for some government official to refuse to list Cruz on the ballot somewhere in some primary, caucus, or election to create an Article III case or controversy. Cruz would almost certainly have standing to assert that he was wrongfully kept off the ballot and seek injunctive and declaratory relief. The state official, in turn, would defend on the ground that Cruz is constitutionally ineligible. And we are off to the races.
So it's easy to create Article III standing. But is the issue nevertheless a political question? I doubt it. It's easy to resolve this question by application of a doctrinal rule. The question is what doctrinal rule applies. It's no different in principle from enforcing the 35-year age requirement. Surely it wouldn't be a political question if a government functionary kept Hillary Clinton off the ballot because he or she asserted that Clinton was actually only 25 years old.
As to the merits, I won't repeat the very interesting discussions that others have written on this question. I agree with Mike Ramsey that it's far from an easy question. But I think that the key theoretical questions involve
(1) whether "natural born citizen" should be understood as a lay member of the public would understand it or whether is a legal term of art;
(2) whether, if it is a legal term of art, it is a fixed concept whose contours are fully determined by practices and understandings existing in 1788, or whether is a common law concept subject to evolutionary development;
(3) whether the meaning of "natural born citizen" depends only on English common law authorities (for example, Blackstone's account in 1765), or whether its application depends, as parts of English common law do, on statutory changes that become established parts of customary practice and thus are absorbed into the constitution-in-practice;
(4) whether the meaning of "natural born citizen," even if vague in 1788, has become liquidated in practice by congressional statutes (like the Naturalization Acts beginning in 1790); and
(5) whether the scope of "natural born citizen" cannot be altered by Congress, or whether it should be read together with Congress's powers under the Naturalization Clause. In the latter case, the Constitution might give Congress the power to determine who is automatically an American citizen at birth and declare such persons natural born citizens for purposes of the Constitution.
My own view-- admittedly preliminary-- is that "natural born citizen" is a legal term of art. It comes from English common law, but it is subject to common law evolution, and therefore it was not fixed for all time in 1788. The best reading of the Eligibility Clause is that "natural born citizen" refers to persons who automatically become citizens at the moment of their birth. But Congress has the power to change (prospectively) who becomes a citizen at birth. If so, then Congress can partially but not completely alter who is a natural born citizen for purposes of Article II.
One might argue that Congress's ability to change the meaning of "natural born" by statute is inconsistent with the term "natural born" because "natural" should be the opposite of "determined by statute." I don't buy this argument. "Natural" in "natural born" doesn't mean "biological." It means "naturally (i.e., automatically) happening without any further intervention."
If we reject the possibility of statutory change, then the determination of who is "natural born" comes not from nature but from English common law. I hope that in the twenty-first century it should be obvious that there's nothing natural about the common law-- and that common law is not more "natural" than statutory law. English common law is also a human artifact, it also changed over time, and it was also made by people with political power, often by fiat and without any democratic accountability.
For this reason, I just don't have a problem concluding that Congress can change who becomes a natural born citizen by expanding or contracting the requirements for automatic citizenship at birth, as long as it does so prospectively.
So to sum up: Under then-existing law at the time of his birth, Cruz automatically became a citizen when he was born in Canada because his mother was a U.S. citizen (and his father had previously resided in the United States). (This also assumes that his mother hadn't surrendered her U.S. citizenship in the meantime.)
Cruz was a natural born citizen because he was automatically born a citizen without any further intervention required. Therefore Cruz is eligible to be President.
I don't assume that the question is open and shut. The issues are complicated, and reasonable minds could differ on the best way to decide it. At the same time, I do think it's pretty easy to create a case or controversy to decide it.