Justice Kennedy's majority opinion in Arizona v. US suggests that the biggest problem with the Arizona immigration measure (SB 1070) is that it conflicts with Congress's (non-existent) right to control what foreigners think of us.
The majority recognizes (as did the Obama administration) that SB 1070 isn't trumped by Congress's constitutional power to establish a "uniform rule of Naturalization." The Ariz. law does not change the rules of naturalization (who can enter the country and under what conditions can they stay); rather, it adds certain state penalties to what are already violations of federal law.
Instead, the majority relies on a mythical all-encompassing federal power over "the status of aliens" -- a power which, according to the majority, flows from the executive's power over foreign affairs. Thus, the federal executive branch must have exclusive control over the mechanisms for enforcing immigration law because of the "fundamental" requirement that foreign countries concerned about the "status, safety, and security of their nationals" must be able to deal with one government, not 50. Justice Kennedy cites the amicus brief filed by Argentina (I kid you not) for the proposition that the federal government must control the "perceptions" that aliens have of this country.
Even assuming that it is a worthwhile goal to give foreign governments the convenience of one-stop shopping and a more friendly "perception" of the US, these considerations must yield to the Constitution. As usual, the money quote is from Scalia's dissent:
The Constitution gives all those on our shores the protections of the Bill of Rights--but just as those rights are not expanded for foreign nationals because of their countries' views . . . neither are the fundamental sovereign powers of the States abridged to accommodate foreign countries' views. Even in its international relations, the Federal Government must live with the inconvenientfact that it is a Union of independent States, who have their own sovereign powers.
By ignoring this "inconvenient fact," the majority casts aside the most basic aspect of state sovereignty: the right to control a state's borders. In the founding era, and for many decades thereafter, the operative assumption was that the states had the exclusive power to exclude undesirable aliens. Jefferson and Madison objected to President Adams' Alien Acts (part of the "Alien and Sedition Acts") on the grounds that the power to determine whether aliens are "dangerous" belonged to the states and had never been delegated to the federal government. In Mayor of New York v. Miln (1837), the Court upheld a New York statute that gave the City the power to turn away any passengers arriving in the Port of New York who the Mayor thought might become a burden on the City.
What we're seeing today is another example of the Court's tendency to interpret the Constitution in a way that the Justices imagine will be most congenial to foreign (mainly European) sensibilities. This approach has already done violence to federalism (e.g., through holdings that the president can invade states' rights via the treaty power); and of course has turned the Eighth Amendment into a mere appendage of the UN Charter.