Can God create a boulder he cannot lift? That's the type of political question raised by the decision in Medellin: namely whether the Bush administration can create a court more resistant to enforcement of international law than the administration itself. And it seems that the answer is "yes."
The decision, boiled down, allows an individual state to put the whole United States in breach of a treaty, in defiance of both an international tribunal and the President's order that the State obey the treaty. If the federal courts are supposed to do anything, it is to prevent individual states from getting the United States into international trouble. That, as Breyer's dissent points out, was the point of the earliest and most important treaty enforcement cases—particularly the Great British Debt case. That case enforced the peace treaty ending the revolutionary war with Britain as against states whose actions threatened a new war. It set out a simple rule: The federal courts need to act to prevent states breaching U.S. treaties. The whole issue of "self-execution" is secondary to this concern.
And with this the Bush administration agreed; it realized that the national interest called for enforcement of the Vienna Convention. Remember that this case is about the treatment of arrested foreign nationals. The worse the United States treats foreign nationals who are arrested, the worse things are for millions of American expatriates.
That's why I disagree with Eric. It's not clear to me how it serves the interest of the whole country to have individual states getting other countries angry at the U.S. That problem in other contexts convinced the Supreme Court to prevent Massachusetts from creating its own sanction regime for Burma ( Crosby ), and convinced it to prevent California from setting up its own claim system for World War II abuses. But in this decision the complexity and weirdness of the "self-execution" doctrine has led the court to miss what is really going on.
The U.S. happens to benefit from enforcement of this particular treaty; hence Bush's order to Texas to enforce the treaty. It's the court, swamped by doctrine and operating outside of the international system that doesn't see that.