Opinion by Judge NOONAN; Dissent Judge GRABER; Partial Dissent and Concurrence in the Dissent by TROTT.
[1155]*1155NOONAN, Circuit Judge:
When a defendant moves under 28 U.S.C. § 2255 to set aside an illegal conviction and a sentence once imposed as part of a plea agreement, should the district court set aside the entire plea agreement, returning the parties to their pre-plea agreement position, or are other remedies provided by § 2255? Our answer to the first alternative is No and to the second, Yes.
PROCEEDINGS
On December 17, 1991 William Scott Barron, Jr. of North Pole, Alaska was indicted on one count of being a felon in possession of a firearm in violation of 18 U.S.C. § 922(g)(1), one count of possession of 21 ounces of cocaine with intent to distribute in violation of 21 U.S.C. § 841(a)(1), and one count of possession of a firearm in relation to a drug trafficking crime in violation of 18 U.S.C. § 924(c)(1). The maximum punishment under the first count was ten years, while the mandatory minimum sentence if the defendant had been convicted of a violent felony or serious drug offense on three previous occasions was 15 years. 18 U.S.C. § 924(a)(2) and (e). The maximum under the second count was life imprisonment and the mandatory minimum was ten years. 21 U.S.C. § 841(b)(1)(A). The sentence under the third count was five years consecutive to any term of imprisonment imposed. 18 U.S.C. § 924(c)(1).
On April 20, 1992 Barron entered into a plea agreement with the United States. The parties acknowledged that the agreement was under, and controlled by, Federal Rule of Criminal Procedure 11(e)(1)(A) and (C).1 Barron agreed to plead guilty to all three counts. agreed to “not seek further prosecution arising out of the facts underlying the present indictment”; to acknowledge that Barron had accepted responsibility; to not seek an enhanced penalty under 18 U.S.C. § 924(e); and to acknowledge that Barron reserved his right to appeal the ruling on his motion to suppress. The parties agreed that Counts one and two should be grouped pursuant to U.S. Sentencing Guidelines Manual § 3D1.2 (1992) in making the sentencing calculation.
On the same date as the agreement was made the district court conducted a hearing at which the government stated that there were “other evidence and other charges that could be brought. We are promising to refrain from bringing those charges, as part of the consideration, and, again, we construe that as part of 11(e)(1)(A), whenever the government is agreeing not to pursue certain charges.” The court referred to Rule 11(e)(1)(C) and inquired what was “the specific sentence that you’ve agreed on as appropriate” under that rule.' The government replied that there was no agreement as to a specific sentence but that “we have agreed that the defendant would not be sentenced pursuant to 924(e) [the armed career criminal statute], which provides a penalty of fifteen years to life.” Defense .counsel noted that, otherwise, there was “at least a possibility that the career offender statute could apply.” The prosecutor added that “the relevant conduct in this case, we do believe could potentially bring the case into the 10-to-life provisions of 841(b).”
The court carefully interrogated the defendant as to whether he knew what he [1156]*1156was pleading to and the numerous constitutional rights such as trial by jury and the right to appeal that he was giving up. The court then formally accepted Barron’s plea. Sentencing was postponed until receipt of the presentencing report. On June 25, 1992 a sentencing hearing was held. Barron’s objections to the presen-tence report were explored. The court sentenced Barron to ten years on the first two counts to run concurrently and to a consecutive term of five years on the gun count.
Three years later the Supreme Court held that to use a gun for purposes of § 924(c)(1) means “active employment” of the firearm in relation to the drug offense. Bailey v. United States, 516 U.S. 137, 143, 116 S.Ct. 501, 133 L.Ed.2d 472 (1995). Barron then moved under 28 U.S.C. § 2255 to set aside his conviction and sentence imposed under 18 U.S.C. § 924(c)(1). The basis for the motion was as follows: “Ground One: Recent Supreme Court decision in Bailey v. United States makes the Petitioner’s conviction under 18 U.S.C. § 924(c) invalid and it should therefore be vacated and dismissed.” Ground One was the sole basis for Barron’s motion.
In argument to the court Barron noted that he had admitted concealing a gun in a safe merely accessible to him, but not to using the gun in the sense required by Bailey. The government conceded that the facts did not justify his conviction on the gun count.
The magistrate judge recommended that Barron’s motion under 28 U.S.C. § 2255 be granted but that at the same time the plea agreement should be rescinded. The district court agreed with those recommendations. According to the district court, Barron by the plea agreement had forfeited “any non-jurisdictional defenses including any defense based upon a favorable intervening change in the law.” The district court, however, went on to hold that Barron could have the plea agreement set aside on the ground that it was not knowing and voluntary because of ignorance of the law declared by Bailey. On motion for reconsideration the district court explained its reasoning:
This Court reasoned that a guilty plea waives, or more accurately forfeits, any right to bring a post-conviction relief petition except one challenging the vol-untariness of the plea.... The Court would therefore have rejected Barron’s § 2255 petition but for the Court’s conclusion that Bailey undermined the pri- or finding of voluntariness. The Court was, and is, prepared to give Barron relief, but solely on the basis that his prior plea was involuntary. The proper relief is to withdraw his plea and' return the parties to the status quo ante.
The court concluded its original order: “Barron’s motion for § 2255 relief should be conditioned on his timely withdrawal of his plea.”
Barron appealed. A panel of this court unanimously affirmed. 127 F.3d 890 (9th Cir.1997). On petition for rehearing, the court divided. 136 F.3d 675 (9th Cir.1998). The full court granted rehearing en banc. 138 F.3d 809 (9th Cir.1998).
ANALYSIS
At the outset it is suggested that Barron must show cause and prejudice in order to be in a position to raise the issue he now presents in his § 2255 motion. Bousley v. United States, 523 U.S. 614, -, 118 S.Ct. 1604, 1611, 140 L.Ed.2d 828 (1998). The government did not raise this objection in the district court or in its briefs on appeal. Ordinarily, the government’s failure to raise the petitioner’s procedural default at the appropriate time waives the defense. See Harmon v. Ryan, 959 F.2d 1457, 1461 (9th Cir.1992). We therefore will usually not allow the government to raise a petitioner’s default for the first time on appeal, when it did not take the opportunity to do so before the district court. See Turner v. Duncan, 158 F.3d 449, 454-55 (9th Cir.1998); Francis v. Rison, 894 F.2d 353, 355 (9th Cir.1990). Because there are no extraordinary circumstances present in this case which would [1157]*1157suggest that justice would be served by overlooking the government’s omission, we treat the procedural default as waived. See Gonzalez v. United States, 33 F.3d 1047, 1049 (9th Cir.1994); cf. Paradis v. Arave, 130 F.3d 385, 390 (9th Cir.1997).
The government argues that Bousley’s clarification of the applicability of procedural default rules in this context represented a new development in the law, which excuses its procedural default. But the government acknowledges that the issue resolved by Bousley was not “so novel that its legal basis [was] not reasonably available to counsel.” Reed v. Ross, 468 U.S. 1, 16, 104 S.Ct. 2901, 82 L.Ed.2d 1 (1984). At the time the Supreme Court granted certiorari in Bousley, the government was litigating the applicability of procedural default rules to challenges based on Bailey in several circuits. See In re Hanserd, 123 F.3d 922 (6th Cir.1997); Lee v. United States, 113 F.3d 73 (7th Cir.1997); United States v. Barnhardt, 93 F.3d 706 (10th Cir.1996). In Bousley itself, the government had raised the procedural default issue at both the district court and the circuit court level. See Bousley v. Brooks, 97 F.3d 284, 287 (8th Cir.1996), rev’d sub nom. Bousley v. United States, 523 U.S. 614, 118 S.Ct. 1604, 140 L.Ed.2d 828 (1998). Bousley was issued five months before the government’s appellate brief was due in this case, yet the government did not raise the procedural default issue here.
Section 2255 grants a prisoner in custody the right “at any time” to bring a motion “to vacate, set aside or correct the sentence” upon the ground that the “sentence was imposed in violation of the Constitution or laws of the United States, or that the court was without jurisdiction to impose such sentence, or that the sentence was in excess of the maximum authorized by law, or is otherwise subject to collateral attack.” 28 U.S.C. § 2255. Of these several grounds, Barron chose one, viz., that the sentence was imposed in violation of the laws of the United States.
The district court agreed with Barron’s contention and so was in the situation envisaged by § 2255 where the court finds “that the sentence imposed was not authorized by law.” At that point the statute instructs the court that it “shall vacate and set the judgment aside” and do one of four things: “discharge the prisoner or resentence him or grant a new trial or correct the sentence as may appear appropriate.” 28 U.S.C. § 2255. The district court accordingly had to vacate the judgment. Although the judgment is a single unitary act, the clear implication of the statute is that vacating the judgment does not prevent the reinstatement of unchallenged counts when the court decides to resentence or to correct the sentence; otherwise, every successful § 2255 petition would result in either discharging the prisoner or granting a new trial. The statutory language forbids elimination of the two possibilities of resentencing or of correcting the sentence. Barron did not contend that he was entitled to be discharged. The district court effectively had three options: grant a new trial, resentence, or correct the sentence. The district court did not have the option of conditionally granting Barron’s motion.
Although Barron did not seek a new trial, the district court chose that option on the ground that Barron’s plea agreement had forfeited an appeal on the basis of “a favorable intervening change in the law,” so that the only way Barron’s motion could be granted was by construing it as an attack on the plea agreement. In this analysis the district court was mistaken for three reasons. First, Barron was not appealing. Second, Bailey was not “a favorable intervening change in the law”; it was a determination that at no time had the law forbidden use of a gun in the sense Barron had used a gun. Third, granting a new trial was not necessary to granting his motion. To grant his motion, the district court did not need to construct an argument against the plea agreement. The district court needed only to resentence.
[1158]*1158Barron’s motion purely and simply asked the district court to vacate a conviction that was void as a matter of law. The motion did not attack the plea agreement in any way. The motion did not assert that Barron had entered the plea agreement unknowingly and involuntarily. The motion did not assert that his conviction of use of a gun was unconstitutional. Barron’s motion proceeded on a recognized basis for seeking federal habeas corpus, viz. that he was confined under a void conviction and therefore under a sentence not authorized by law. James S. Liebman & Randy Hertz, Federal Habeas Corpus Practice and Procedure § 41.3b at 1192 (2d ed.1994). It is only the analysis of the district court that turned this simple motion into something more, a challenge to the plea agreement. The district court had no authority to invent a new basis for Barron’s motion and erred in doing so.
It is urged that a guilty plea is “a single act,” so that it cannot be half knowing and half ignorant. This argument assumes a ground for the § 2255 motion that Barron did not advance. The argument might be rephrased to state that a guilty plea cannot be only partly set aside. This argument is parallel to the argument that, as there is only one judgment, it cannot be vacated and then reinstated in part. These arguments have the ring of metaphysical abstraction. As a practical matter, in § 2255 proceedings judgments are vacated and then reinstated to cover only the valid convictions remaining. E.g., United States v. Handa, 122 F.3d 690 (9th Cir.1997), cert. denied, - U.S. -, 118 S.Ct. 869, 139 L.Ed.2d 766 (1998). As a practical matter, the guilty plea to criminal acts can remain in force even as the sentence imposed upon an innocent act is set aside. Nor is there any more reason for reducing § 2255 remedies to two (discharge or new trial) when a plea agreement is in force. Just as in thé case of vacating a judgment after trial, the district court can distinguish the convictions that are still valid, reinstate the judgment, and resentence. We, along with seven other circuits, followed this procedure in Handa.
The government approaches the question from contract law, an angle distinct from that of the district court. The government argues that Barron breached the agreement by attacking his § 924 conviction and sentence; therefore, there has been a failure of consideration and the government is no longer bound by the agreement. Alternatively, the government contends that there was a mutual mistake of law; the mistake justifies rescission. Restatement (Second) of Contracts § 152 (1981 & Supp.1996). The government accurately observes that we have frequently analyzed plea bargains on contract principles. See, e.g., United States v. Escamilla, 975 F.2d 568, 571 (9th Cir.1992). To seek to set aside a conviction for conduct that is innocent is neither to breach nor to repudiate the agreement. United States v. Sandoval-Lopez, 122 F.3d 797, 802 (9th Cir.1997). The plea agreement is not at issue.
Not only is the government mistaken in treating Barron’s motion as an attack on the plea agreement, but as the government acknowledges its reliance on contract law is by analogy, and the analogy is not perfect. United States v. Partida-Parra, 859 F.2d 629, 634 (9th Cir.1988). A plea bargain is not a commercial exchange. It is an instrument for the enforcement of the criminal law. What is at stake for the defendant is his liberty. On rescission of the agreement, the prisoner can never be returned to his “original position”: he has served time by reason of his guilty plea and his surrender of basic constitutional rights; the time he has spent in prison can never be restored, nor can his cooperation in his punishment. What is at stake for the government is its interest in securing just punishment for violation of the law and its interest that an innocent act not be punished at all. The interests at stake and the judicial context in which they are weighed require that something more than contract law be applied. This court has on other occasions declined to extend the contract law analogy to invalidate a plea bargain based on a mutual mistake of law. [1159]*1159See United States v. Zweber, 913 F.2d 705, 711 (9th Cir.1990); Partida-Parra, 859 F.2d at 634.
The government frames the issue as whether, in the light of Bailey, Barron may move, pursuant to § 2255, to vacate his conviction. Phrased in those terms, the answer has to be, “Of course.” The government in its brief actually says: “We do not, of course, suggest that appellant should have been required to serve the full 60-month sentence that Bailey had invalidated.” That proposition, “Serve out your invalid sentence,” is repudiated by the government. But, after repudiating this proposition, the government reinstates it by adding: “[T]he proper remedy ... [is] to return the parties to their initial positions,” i.e., for Barron to get rid of his five year invalid sentence he must run the risk of prosecution for a crime entailing a life sentence. The government gives with one hand and takes away with the other.
Starkly put, the government is in effect saying, “Serve out your extra five years even though you are innocent; otherwise be prepared to risk imprisonment for life as an armed career criminal even though we agreed in 1991 that we would not charge you with this crime.” Cushioned in contract law, the government’s claim may not seem wholly unreasonable. Stripped of the contract analogy, the government’s position is untenable. As an initial matter the government could not have said, “You are innocent of using a gun, but if you’ll plead to it, we’ll give up charging you for your career offenses.” Unless the government can do the same thing now by invoking contract principles, its case is no bet- . ter.
The first dissent offers an analysis different from that of the magistrate judge, the district judge, the government in the district court and on appeal, and the majority. The dissent asserts: “UNDER 28 U.S.C. § 2255, THE DISTRICT COURT WAS OBLIGED TO GRANT A NEW TRIAL” (capitals in original). The dissent continues its analysis by stating: “[H]e [Barron] claimed that his conviction for violation of 18 U.S.C. § 924(c)(1) should be vacated, because it was procured in violation of his constitutional rights” (emphasis in original). This statement is made in error. Barron sought to set aside his sentence and, as a ground, claimed that his conviction was void because it was not authorized by law. The dissent proceeds on a mistaken assumption.
The dissent quotes § 2255 but unaccountably overlooks that the only motion authorized by that statute must begin with a claim as to the sentence. What a prisoner is complaining about when habeas is sought is the imprisonment. By the terms of the statute the prisoner has to attack the sentence, and Barron did so. The dissent goes on to assert that Barron’s sentence was “authorized by law” in the sense that the sentence matched the crime of which he stood convicted. This contention is a total abstraction from the facts. If the dissent’s construction of “authorized by law” were correct, no sentence that corresponded to the crime of conviction could be set aside even when the prisoner demonstrated complete innocence of the crime. As everyone agrees, Barron should not have been convicted of this crime. The conviction was therefore not authorized by law, and neither was the sentence.
The dissent asserts that the district court must vacate the judgment. On that point there is no dispute. The dissent, however, goes on to say: “Structurally, when the error permitting § 2255 relief lies in the entry of particular convictions, the permissible remedies are the discharge of the prisoner or the granting of a new trial as to the unconstitutional convictions” (emphasis in original). Here, too, we are in agreement. The dissent then goes on, however, to discuss United States v. Marchese, 341 F.2d 782 (9th Cir.), cert. denied, 382 U.S. 817, 86 S.Ct. 41, 15 L.Ed.2d 64 (1965). In that case, after a jury trial the defendants contended that their convictions had been obtained unconstitutionally. Id. at 787. The district court agreed and reduced their sentences [1160]*1160from ten to five years. Id. at 786. We held that the sentences could not be reduced “without vacating the conviction.” Id. at 788. We said, “If the court vacates and sets aside the judgment of conviction, then, of course, the prisoner must be discharged, or granted a new trial.” Id. The dissent makes this single sentence of Márchese stand not only for the uncontroversial proposition that the only way an illegal conviction can be corrected is by discharging the prisoner or granting a new trial, but it then contradicts its earlier statement and implies that all the valid counts of conviction must likewise be set aside. Márchese says no such thing. The dissent indeed repeats this erroneous implication, stating: “[T]he usual remedy following a successful collateral attack on a conviction resulting from a trial is a new trial.” To the contrary, the usual remedy is to set aside the counts on which illegal convictions were obtained and to leave untouched the valid convictions. If the sentence of Márchese were literally true in all circumstances, successful § 2255 petitions would regularly lead to a new trial, even though a conviction on only one count was challenged. That is not the way § 2255 petitions are normally handled. See, e.g., United States v. Handa, 122 F.3d 690; Keating v. United States, 413 F.2d 1028 (9th Cir.1969) (resentence after vacating judgment and vacating one of two convictions). If it were otherwise, the successful challenge of one count might force the government to try other valid counts where the evidence would be stale or dispersed. Section 2255 would become a nightmare for prosecutors.
Márchese was simply a case where a district judge erred and was reversed because he reduced the sentence without finding the convictions or sentence illegal and without vacating the underlying judgment. The dissent concludes its discussion of Márchese by asserting that we make the same error by ordering resentencing when the petitioner’s conviction was obtained unlawfully. What the dissent fails to note is that, unlike Márchese, we are not ordering resentencing on the challenged count but only permitting it on the indisputably valid ones. The claim that Márchese forbids the relief that the majority requires is wholly unwarranted.
In United States v. Handa we embraced the packaging metaphor as enunciated by the Seventh Circuit and adopted by the District of Columbia, First, Third, Fourth, Fifth, and Eighth Circuits. 122 F.3d at 691-92. We held that the “broad and flexible power” conferred by § 2255 authorized the district court, after setting aside an invalid conviction, to re-sentence on the remaining crimes of which the defendant stands convicted. Id. at 691. We do not repudiate this holding; rather, we affirm it so "that the district court may vacate the judgment and resen-tenee Barron on the two counts of conviction that still stand, taking into account any relevant enhancement under the Sentencing Guidelines. The dissent, despite lip service to Handa, effectively would overrule it.
The dissent argues that “the unitary nature of the entry of a plea of guilty to multiple counts” forecloses such a remedy in the instant case. However, the argument that plea bargains must be treated as a package logically applies only in cases in which a petitioner challenges the entire plea as unknowing or involuntary. The dissent relies not on the statutory language of § 2255 but rather on United States v. Gerard, which held that a defendant who successfully withdraws from a plea agreement may not object to revival of counts previously dismissed. 491 F.2d 1300, 1305-06 (9th Cir.1974). The dissent ignores that our subsequent decision in United States v. Sandoval-Lopez, limited Gerard in holding that, unlike a claim that the plea agreement itself was unknowing or involuntary, a collateral challenge to the legality of a particular count of conviction does not constitute a breach of or withdrawal from a plea agreement, and that the remainder of the plea agreement remains in effect. 122 F.3d at 801-02. Moreover, the dissent offers no statutory [1161]*1161authority for vacating counts of conviction that have not been challenged by a § 2255 petitioner.
The drafter of the plea agreement could have anticipated the contingency that has arisen and included a provision protecting the government’s interest in the event that Barron’s conviction was vacated; that the government did not do so does not justify recission of the agreement. See id.
The second dissent follows the government’s tack in pressing the analogy between a plea bargain and a contract without acknowledging the differences that are relevant here. This dissent also adopts the approach of the district court in speculating about how to decide a case not before us and strangely underestimates the government’s ability to provide in the plea agreement for the contingency that has arisen. That contingency is not, as this dissent erroneously maintains, a change in the law but an authoritative declaration of what the law is. Most notably, the second dissent discussing a procedure that is governed by statute fails to focus on the statute at all. At the North Pole, as in the nation’s capital, the search for justice starts with the statute.
Reducing the district court’s options to the single option of granting a new trial may sometimes favor the government, sometimes the defendant. The issue should not be decided on the basis of which party is aided but on the basis of what the statute grants: the power to resentence after vacating a judgment that imposed a sentence not authorized by law. The statute incorporates the fundamental principle that it is never just to punish a man or woman for an innocent act. Accordingly, we reverse the district court and remand for further proceedings consistent with this opinion.
REVERSED AND REMANDED