concurring in part and dissenting in part, and joined by EBEL, J., as to Section IV, and LUCERO, J., as to Section V.
I agree with the majority that with the issuance of United States v. Booker, — U.S. -, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005), we must now conclude the district court erred by applying the Sentencing Guidelines in a mandatory rather than advisory fashion at the time it sentenced Gonzalez-Huerta. Although I agree that this error was neither constitutional nor structural in nature, I disagree that the error does not warrant correction. When Gonzalez-Huerta was sentenced, no one in the courtroom — neither the district court nor counsel — knew of or applied the correct law. In my view, this error not only affects Gonzalez-Huerta’s substantial rights, it also seriously affects the fundamental fairness, integrity, or public reputation of judicial proceedings. Accordingly, I would remand this case for resentencing.
I.
In September 2003, Gonzalez-Huerta was indicted by a federal grand jury on one count of reentry by a deported alien previously convicted of an aggravated felony, in violation of 8 U.S.C. § 1326. Gonzalez-Huerta pled guilty to that charge in November 2003, and was sentenced by the district court on March 1, 2004. At the time of sentencing, Gonzalez-Huerta admitted all of the relevant facts set forth in *748the presentence investigation report, including the fact of his prior conviction. Based upon those admitted facts, the district court sentenced Gonzalez-Huerta to 57 months’ imprisonment, a sentence at the bottom of the applicable guideline range (57-71 months). Judgment was entered by the district court on March 2, 2004, and Gonzalez-Huerta filed a notice of appeal on March 8, 2004.
As these facts indicate, Gonzalez-Huerta’s sentencing on March 1, 2004, predated the Supreme Court’s rulings in both Blakely v. Washington, — U.S. -, 124 S.Ct. 2531, 159 L.Ed.2d 403 (2004), and Booker (January 12, 2005). Although Apprendi v. New Jersey, 530 U.S. 466, 120 S.Ct. 2348, 147 L.Ed.2d 435 (2000), predated Gonzalez-Huerta’s sentencing, its holding that any fact increasing a sentence beyond the statutory maximum must be submitted to a jury was seemingly inapplicable to Gonzalez-Huerta’s case, since Gonzalez-Huerta’s sentence did not exceed the statutory maximum penalty and the district court did not engage in any fact-finding. Not until after Gonzalez-Huerta had filed his notice of appeal did the Supreme Court issue Blakely and indicate, in the context of a Washington state case, that the “statutory maximum sentence” for Apprendi purposes is the maximum guideline sentence a judge may impose solely on the basis of the facts reflected in the jury verdict or admitted by the defendant.
On September 16, 2004, Gonzalez-Huerta filed his original appellate brief asserting in pertinent part that, in light of Blakely, “the federal Sentencing Guidelines [we]re unconstitutional and not severable.” Aplt. Br. at 4. Following the issuance of Booker, we directed the parties to file supplemental briefs. Gonzalez-Huerta now asserts that the district court erred in sentencing him because, contrary to Booker, it applied the Sentencing Guidelines in a mandatory rather than advisory fashion. Gonzalez-Huerta further argues that this error was both constitutional and structural in nature. Accordingly, Gonzalez-Huerta contends he is entitled to be resen-tenced.
II.
In Booker, the Supreme Court addressed two questions: “whether [its] Ap-prendi line of cases applies to the Sentencing Guidelines, and if so, what portions of the Guidelines remain in effect.” 125 S.Ct. at 747. With respect to the first question, the Court held that its Apprendi line of cases, including Blakely, “applies to the Sentencing Guidelines.” Id. at 755. Thus, “[a]ny fact (other than a prior conviction) which is necessary to support a sentence exceeding the maximum authorized by the facts established by a plea of guilty or a jury verdict must be admitted by the defendant or proved to a jury beyond a reasonable doubt.” Id. at 756. As for the second question, the Court, in what can be referred to as its “remedial holding,” “answered] the question of remedy by finding the provision of the federal sentencing statute that makes the Guidelines mandatory, 18 U.S.C.A. § 3553(b)(1) (Supp.2004), incompatible with [its] constitutional holding.” Id. More specifically, the Court “conclude[d] that this provision must be severed and excised, as must one other statutory section, § 3742(e) (main ed. and Supp.2004), which depends upon the Guidelines’ mandatory nature.”1 Id. at 756-57. The result, the Court held, was to “make[ ] the Guidelines effectively advisory.” Id. at 757. In other words, the Court held, “[i]t requires a sentencing *749court to consider Guidelines ranges, see 18 U.S.C.A. § 3553(a)(4) (Supp.2004), but it permits the court to tailor the sentence in light of other statutory concerns as well, see § 3553(a) (Supp.2004).” Id.
In its remedial holding in Booker, the Court outlined how its decision was to be applied:
[W]e must apply today’s holdings — both the Sixth Amendment holding and our remedial interpretation of the Sentencing Act — to all cases on direct review, (citations omitted). That fact does not mean that we believe that every sentence gives rise to a Sixth Amendment violation. Nor do we believe that every appeal will lead to a new sentencing hearing. That is because we expect reviewing courts to apply ordinary prudential doctrines, determining, for example, whether the issue was raised below and whether it fails the “plain-error” test. It is also because, in cases not involving a Sixth Amendment violation, whether resentencing is warranted or whether it will instead be sufficient to review a sentence for reasonableness may depend upon application of the harmless-error doctrine.
125 S.Ct. at 769.
At least four directives can be drawn from this language. First, Booker is to be applied retroactively to cases, such as Gonzalez-Huerta’s, that were pending on direct review at the time of Booker’s issuance. Second, not every case pending on direct review at the time of Booker’s issuance will involve a Sixth Amendment sentencing violation or require a new sentencing hearing. Third, “ordinary prudential doctrines,” including the plain error test, are expected to be applied to cases pending on direct review at the time of Booker’s issuance. Finally, the resolution of cases pending on direct review that do not involve a Sixth Amendment violation may hinge upon application of the harmless-error doctrine.
Application of these directives requires a reviewing court to first determine the type of error(s) at issue. As Booker makes clear, a case pending on direct review at the time of the opinion’s issuance can potentially involve (a) a Sixth Amendment violation resulting from the district court’s enhancement of the defendant’s sentence based upon judicially-found facts, (b) a violation of Booker’s remedial holding, i.e., the district court’s treatment of the Sentencing Guidelines as mandatory rather than discretionary, or (c) both. After determining the type of alleged error(s) at issue, a reviewing court must then determine whether the defendant raised the issue(s) below and, in turn, the standard of review that should be applied to the alleged error(s).
III.
Turning to Gonzalez-Huerta’s appeal, it is undisputed that he has asserted one Booker-related error, i.e., that the district court in his case applied the Sentencing Guidelines in a mandatory rather than discretionary fashion (what the majority refers to as “non-constitutional Booker error”).2 The next question, and the one on which our en banc review is most heavily focused, is what standard of review to apply to that alleged error.
Generally speaking, we apply one of two standards of review to errors arising in criminal cases. Which standard of review will apply depends upon whether or not the defendant asserted a timely objection *750to the error in the district court. If the defendant timely objected, the error is generally considered to be “nonforfeited,” and we in turn apply the “harmless error” standard outlined in Federal Rule of Criminal Procedure 52(a). United States v. Olano, 507 U.S. 725, 731, 113 S.Ct. 1770, 123 L.Ed.2d 508 (1993). Under that standard, “[ajny error ... that does not affect substantial rights must be disregarded.” Fed.R.Crim,P. 52(a). If the defendant did not timely object to the error, it is generally considered “forfeited,” and we in turn apply the “plain error” standard outlined in Federal Rule of Criminal Procedure 52(b). Olano, 507 U.S. at 731, 113 S.Ct. 1770. Under Rule 52(b), a court of appeals may correct (1) an error, (2) that is plain, and (3) that affects substantial rights, but only if (4) the error seriously affects the fairness, integrity, or public reputation of judicial proceedings. United States v. Cotton, 535 U.S. 625, 631, 122 S.Ct. 1781, 152 L.Ed.2d 860 (2002). Although Rule 52(a) and Rule 52(b) “require[ ] the same kind of inquiry,” there is one important difference between them: in plain error cases “[i]t is the defendant rather than the Government who bears the burden of persuasion with respect to prejudice.” Olano, 507 U.S. at 734, 113 S.Ct. 1770.
The difficulty we face in this case is that the error asserted by Gonzalez-Huerta does not fit neatly within either of these-two categories. To be sure, Gonzalez-Huerta did not assert the error below and instead is raising it for the first time on appeal. If we were to consider only that fact, it would be easy to classify the error as “forfeited” and then move to a straightforward application of the plain error standard outlined in Rule 52(b). To do so, however, would ignore the realities of this case. At the time Gonzalez-Huerta was sentenced, the Federal Sentencing Act made application of the United States Sentencing Guidelines mandatory. See 18 U.S.C. § 3553(b)(1). Further, it is safe to say that no one at that time, including Gonzalez-Huerta and the district court, could have predicted the absolute sea-change in federal sentencing that would ultimately be wrought by the Supreme Court in its Booker remedial holding, i.e., severing and excising “the provision of the federal sentencing statute that makes the Guidelines mandatory,” 125 S.Ct. at 756, so as to render the Guidelines advisory. Thus, in contrast to the overwhelming majority of plain error cases, it is unreasonable in my view to conclude that Gonzalez-Huerta could and should have raised the issue below. See O’Connor v. Ohio, 385 U.S. 92, 93, 87 S.Ct. 252, 17 L.Ed.2d 189 (1966) (refusing to punish criminal defendant for failing to anticipate a new constitutional rule recognized during the pen-dency of his direct appeal); United States v. Viola, 35 F.3d 37, 42 (2d Cir.1994) (“If we were to penalize defendants for failing to challenge entrenched precedent, we would be insisting upon an omniscience on the part of defendants about the course of the law that we do not have as judges. Imposing such a duty would only encourage frivolous objections and appeals.”), abrogated on other grounds, Salinas v. United States, 522 U.S. 52, 65-66, 118 S.Ct. 469, 139 L.Ed.2d 352 (1997); see generally United States v. Dominguez Benitez, 542 U.S. 74, 124 S.Ct. 2333, 2340, 159 L.Ed.2d 157 (2004) (noting that one of the primary policies underpinning Rule 52(b) is “to encourage timely objections”). It therefore strikes me as disingenuous, as well as unfair, to treat Gonzalez-Huerta’s error like the vast majority of other plain errors, and in turn to require Gonzalez-Huerta to satisfy the typical plain error,standard.3
*751Gonzalez-Huerta’s case also fails to fit neatly within the plain error framework for another reason. As noted, a plain error cannot be corrected unless it affects a defendant’s substantial rights. Olano, 507 U.S. at 734, 113 S.Ct. 1770. “[I]n most cases,” this means “that the error must have been prejudicial: It must have affected the outcome of the district court proceedings.” Id. Typically, an appellate court applying the plain error test is able to make a reasonable determination of an error’s prejudicial effect on the district court proceedings by reviewing the record on appeal. E.g, Johnson v. United States, 520 U.S. 461, 470, 117 S.Ct. 1544, 137 L.Ed.2d 718 (1997) (concluding that, despite district court’s plain error of deciding the issue of materiality, i.e., Gaudin error, in a perjury prosecution rather than submitting it to the jury, there was no basis for reversal because “the evidence supporting materiality was ‘overwhelming’ ”); Harrington v. California, 395 U.S. 250, 254, 89 S.Ct. 1726, 23 L.Ed.2d 284 (1969) (“Our judgment must be based on our own reading of the record and on what seems to us to have been the probable impact of the” error at issue). Here, however, Gonzalez-Huerta’s sentencing proceedings were conducted by the district court under what we now know was the mistaken assumption that the Sentencing Guidelines were to be applied in a mandatory fashion. Thus, there was no opportunity or incentive, as there is now post-Booker, for Gonzalez-Huerta or the government to present evidence or arguments outside of the bounds allowed by the Guidelines.4 See United States v. Barnett, 398 F.3d 516, 528 (6th Cir.2005) (“Under the new post -Booker framework, the district court is empowered with greater discretion to consider the factors provided in 18 U.S.C. § 3553(a) in determining a proper sentence.”); United States v. Crosby, 397 F.3d 103, 115 (2d Cir.2005) (“It will ... be impossible to tell what considerations counsel for both sides *752might have brought to the sentencing judge’s attention had they known that they could urge the judge to impose a non-Guidelines sentence.”); United States v. Jaber, 362 F.Supp.2d 365, 383, No. CRIM.02-10201-NG, 2005 WL 605787, at *15 (D.Mass.2005) (taking into account, under § 3553(a), the fact that the defendant was on salary and did not take a profit from the drug organization, the fact that the defendant engaged in no criminal conduct during the two years prior to his arrest, and the fact that the defendant’s post-conviction, pre-sentencing record was “perfect,” even though his wife was “hospitalized and dysfunctional,” his residence was foreclosed, and he was unable to find a meaningful job); United States v. Ranum, 353 F.Supp.2d 984, 985-86 (E.D.Wis.2005) (concluding that factors formerly forbidden to be considered under the Guidelines, such as a defendant’s age, family ties and responsibilities, and physical, mental and emotional condition, may now be considered, post -Booker, pursuant to § 3553(a)); see also Steven G. Kalar, Booker Advisory: Into the Breyer Patch, 29 Champion 8, 15 (Mar.2005) (suggesting that the “prohibited or discouraged departure” factors listed in Chapter 5H of the Guidelines “are tailor-made for the broader equitable analysis” that will now apply under Booker). Likewise, there was no reason for the district court to give serious consideration to whether a sentence other than that suggested by the Guidelines was appropriate, nor was there any incentive for the district court to voice concerns about the operation of the Guidelines. See Barnett, 398 F.3d at 528-29. In sum, because the entire legal framework in which Gonzalez-Huerta’s sentencing occurred was flawed, there is no way for him to prove, and for us to accurately assess, the likelihood that the district court would have imposed a different sentence had it known it had the discretion to do so. In other words, “it would be exceedingly difficult for” Gonzalez-Huerta “to show that his sentence would have been different if the district court had sentenced him under [an] advisory, rather than the mandatory, Guidelines framework.” Id. at 528; see also United States v. Paladino, 401 F.3d 471, 481-82 (7th Cir.2005) (noting the difficulty of assessing the effect of a sentencing error because “sentencing ... is the choice of a point within a range established by Congress, and normally the range is a broad one”); id. at *482 (recognizing “the impossible burden of proving that the sentencing judge would have imposed a different sentence had the judge not thought the guidelines mandatory”); Labastida-Segura, 396 F.3d at 1143 (applying harmless error standard to non-constitutional Booker error and concluding it was impossible to determine what sentence would have been imposed by the district court under an advisory Guidelines framework).
The majority quickly moves past this problem, suggesting only that prejudice might be found to exist if there are statements in the record from the sentencing court expressing dissatisfaction with the Guidelines sentence it believed, at the time, it was required to impose. Focusing the prejudice analysis on such evidence, however, ignores the reality of the pre-Booker sentencing landscape. It is beyond dispute that the federal circuits, including our own, “repeatedly instructed sentencing courts pre-Booker to impose sentences within the applicable mandatory Guidelines range, with limited exceptions, and ... consistently upheld the constitutionality of the Guidelines and their mandatory nature .... ” Barnett, 398 F.3d at 528. In turn, “[t]his well-established case law substantially undermined any need or incentive for sentencing courts pre-Booker to note their objections and reservations in sentencing defendants under the then-*753mandatory Guidelines.” Id. at 529; see also Heldeman, 402 F.3d at 224, 2005 WL 708397, at *3 (“we have recognized that a district judge [pre-Booker] may well not have expressed his or her reservations because the guidelines made them hopeless”); Paladino, 401 F.3d at 482-83, (suggesting that, pr e-Booker, “[a] conscientious judge” was “one who took the guidelines seriously whatever his [or her] private views”). Thus, I agree with the Sixth Circuit that “[i]t would be improper,” and indeed cruelly ironic, for us to now “require defendants such as” Gonzalez-Huerta “to produce this type of evidence — -that sentencing courts had no reason to provide under our pr e-Booker case law — in order to establish that their substantial rights have been affected.” Barnett, 398 F.3d at 529.
IV.'
Olano itself provides a way out of this thicket by recognizing that the prejudice component (or the so-called “third prong”) of the plain error test can be modified in extreme cases:
We need not decide whether the phrase “affecting substantial rights” is always synonymous with “prejudicial.” (citation omitted). There may be a special category of forfeited errors that can be corrected regardless of their effect on the outcome, but this issue need not be addressed. Nor need we address those errors that should be presumed prejudicial if the defendant cannot make a specific showing of prejudice. Normally, although perhaps not in every case, the defendant must make a specific showing of prejudice to satisfy the “affecting substantial rights” prong of Rule 52(b).
507 U.S. at 735, 113 S.Ct. 1770 (emphasis added). This language recognizes two possible exceptions to the “normal” formulation of the third prong. The first of these exceptions is for “structural errors,” i.e., the so-called “special category of forfeited errors that can be corrected regardless of their effect on the outcome.” Id. at 735, 113 S.Ct. 1770; see Barnett, 398 F.3d at 526 (interpreting Olano in this manner); see also United States v. Dominguez Benitez, 542 U.S. 74, 124 S.Ct. 2333, 2339, 159 L.Ed.2d 157 (2004) (noting that only structural errors can entitle, a- defendant to relief “without regard to [their] effect on the proeeeding[s]”); Cotton, 535 U.S. at 632, 122 S.Ct. 1781 (suggesting the Court in Olano was referring to structural errors). Although Gonzalez-Huerta contends the error at issue is structural in nature, I agree with the majority that it is not.5 That still leaves, however, the sec*754ond potential exception recognized in Ola-no, i.e., errors that “should be presumed prejudicial if the defendant cannot make a specific showing of prejudice.” 507 U.S. at 735, 113 S.Ct. 1770. Obviously, this language was meant to refer to something other than structural errors. See Dominguez Benitez, 124 S.Ct. at 2339 (noting that, other than for structural errors, “relief for error is tied in some way to prejudicial effect”); Barnett, 398 F.3d at 526-27.
Like the Sixth Circuit in Barnett, I conclude that the error asserted by Gonzalez-Huerta falls within this second exception. 398 F.3d at 527-28 (“We are convinced that this is an appropriate case in which to presume prejudice under the Supreme Court’s decision in Olano.”). To begin with, it is apparent, for the reasons outlined above, that the task of making a specific showing of prejudice is nearly impossible for Gonzalez-Huerta and others situated similarly to him, i.e., that “set” of defendants who were sentenced prior to Booker and Blakely. Notwithstanding that fact, the available post-Booker data allows us to say with reasonable probability, and perhaps near-certainty, that some of the defendants within this “set” were in fact prejudiced by application of the mandatory Guideline regime. On March 22, 2005, the United States Sentencing Commission’s Office of Policy Analysis issued a memorandum compiling data on post-Booker sentencings as of the close-of-business on March 15, 2005. Linda D. Max-field, U.S. Sentencing Comm’n, Data Extract on March 15: Numbers on Post-Booker Sentencings (Mar. 14, 2005) (available at http://www.ussc.gov/Blakely/booker — 030305.pdf). According to that data, approximately 36.0 percent of all post-Booker sentences were below the advisory Guideline range. Further, approximately 13.7 percent of all post -Booker sentences were below the advisory Guideline range for a reason other than a government-sponsored reduction.6 Extrapolating from this data, it appears reasonable to assume that perhaps as many as 13.7 percent of all the defendants in our Booker plain-error set of cases, or approximately one out of every seven such defendants, would receive a below-Guideline sentence if they were sentenced under a discretionary Guideline regime. In other words, there is some data to suggest that one out of every seven of such defendants were prejudiced by application of the pre-Booker mandatory Guideline regime. Further, if we confine' our analysis to only those defendants who, like Gonzalez-Huerta, received a pre-Booker sentence at the very bottom of the applicable Guideline range, it appears safe to assume that the percentage actually prejudiced by the mandatory application of the Guidelines is higher. I therefore conclude that the “most prudent course of action” in these unique circumstances is to apply the second Olano exception and presume prejudice. Id. at 529.
Although Olano provides ample support for application of the presumption of prejudice approach, I believe there is another *755source of case law that provides additional support. Our court and other circuits have recognized the “supervening-decision doctrine.” See United States v. Santiago, 238 F.3d 213, 215 (2d Cir.2001) (noting that when source of error is supervening judicial decision that alters settled law, it is appropriate to modify the third prong of the plain error rule so that the government bears the burden of persuasion); United States v. Washington, 12 F.3d 1128, 1139 (D.C.Cir.1994) (recognizing doctrine and noting that it “reflects the principle that it would be unfair, and even contrary to the efficient administration of justice, to expect a defendant to object at trial where existing law appears so clear as to foreclose any possibility of success.”); see also Anixter v. Home-Stake Prod., 77 F.3d 1215, 1231-32 (10th Cir.1996) (applying similar doctrine in civil case); United States v. Zeigler, 19 F.3d 486, 494 (10th Cir.1994) (appearing to apply similar approach where government objected to defendant’s sentence for the first time on appeal based on intervening Supreme Court decision that effectively overruled circuit precedent). This doctrine, which appears to be rooted in Ola-no7, recognizes that “[a] defendant clearly has no duty to object to [something] that is based on firmly established circuit authority,” and thus “cannot be said to have ‘forfeited a right’ by not making an objection, since at the time of trial no legal right existed.” Viola, 35 F.3d at 42. Cases falling within the scope of this doctrine are treated in a manner similar to “harmless error review under Rule 52(a),” thereby requiring “the government [to] show that the error did not affect the defendant’s substantial rights.” Id. The “presumption of prejudice” approach appears to achieve much the same result as the supervening decision doctrine, albeit by modifying the analysis under the third prong of the plain error test rather than by channeling the case into the harmless error framework.
In comparison to slavishly applying the traditional formulation of the third prong of the plain error test, adopting the “presumption of prejudice” approach will undoubtedly result in more of the relatively small set of plain-error Booker cases being remanded for resentencing. The costs associated with that result, however, are minimal in my view, particularly in comparison to the benefits of ensuring that defendants are not subjected to unnecessary and improper deprivations of their liberty. See United States v. Serrano-Beauvaix, 400 F.3d 50, 61 (1st Cir.2005) (Lipez, J., concurring) (“Given what is at stake in sentencing decisions — the potential for additional months or even years in prison — I believe that the increased administrative burdens are a tolerable price to pay.”); United States v. Williams, 399 F.3d 450, 456 (2d Cir. Feb.23, 2005) (“A resentencing is a brief event, normally taking less than a day and requiring the attendance of only the defendant, counsel, and court personnel.”); Barnett, 398 F.3d at 532 (Gwin, J., concurring) (“In summary, an unnecessarily restrictive plain error analysis will result in substantial additional work for this court and will save the district courts almost no time. * * * I believe it more efficient to remand this case to the district court for re-sentencing. Otherwise, we adopt a rule that results in an inordinate expenditure of appellate *756court resources, yet saves the district court little.”).
The majority expresses three reservations about adopting the “presumption of prejudice” approach. In my view, none of those reservations are persuasive. First, they assert that “in the twelve years since its decision in Olano, the [Supreme] Court has never again mentioned this category of presumed prejudice — let alone applied it to an analogous factual scenario.” Maj. Op. at 13. Although this statement is true, it is equally true that the Supreme Court has never expressly repudiated the language in Olano discussing the category of presumed prejudice. Further, the majority cannot, in my view, point to any case that has come before the Supreme Court since Ola-no that has presented such a compelling case for application of that “presumed prejudice” exception. Indeed, if the error now asserted by Gonzalez does not fall within this exception, then I seriously question if any case ever will. Moreover, the majority overlooks the various post-Olano circuit cases that have applied the “presumption of prejudice” approach to other errors, e.g,, Barnett, 398 F.3d at 526-27 (cataloging cases), as well as the cases cited above which have applied the supervening-decision doctrine.
Second, the majority suggests that because in some cases “the sentencing judge [may have] expressed unhappiness with the mandatory nature of the Guidelines on the record,” “establishing that non-constitutional Booker error affects substantial rights is not an impossible task.” Maj. Op. at 14. For the reasons already discussed, the fact that a handful of such cases may exist is not, in my view, a reasonable basis for rejecting the “presumption of prejudice” approach.
Third, the majority questions the “presumption of prejudice” approach because “placing the burden on the appellant is one of the essential characteristics distinguishing plain error from harmless error,” and “[sjhifting the burden to the appellee would seriously blur this distinction and would be inconsistent with our precedent.” Maj. Op. at 736. Again, for the reasons already discussed, it is apparent that this case and others like it do not fit neatly within either the harmless error or the plain error framework, and thus demand some type of meaningful exception. The fact that the “presumption of prejudice” approach may “blur th[e] distinction” between the two standards is not, in my view, a meaningful basis on which to reject the approach, particularly since the “presumption of prejudice” approach originated with the Supreme Court and not the lower federal courts, and because the approach is obviously suited for an exceedingly narrow range of cases. As for the alleged inconsistency between the “presumption of prejudice” approach and our precedent regarding plain error, the majority does not point to any cases similar to the one at hand, nor can it point to any cases in which we have rejected the “presumption of prejudice” approach.
•V.
With this modification of the burden of persuasion with respect to prejudice in place, I now turn to application of the plain error test. The first two prongs of the plain error test, i.e., was there (1) an error that (2) was plain, cannot seriously be disputed in this case.8 In light of the remedial holding in Booker, it is apparent that the district court in this case erred in treating *757the Guidelines as mandatory rather than advisory. Although this error was not “plain” at the time of Gonzalez-Huerta’s sentencing (since Booker had not yet been issued at that time), it is the law at the time of the appellate decision that is relevant here. See Johnson, 520 U.S. at 468, 117 S.Ct. 1544 (holding that “where the law at the time of trial was settled and clearly contrary to the law at the time of appeal — it is enough that the error be ‘plain’ at the time of appellate consideration.”). Thus, in light of the remedial holding in Booker, the error is now plain. E.g., Barnett, 398 F.3d at 525-26.
Applying the presumption of prejudice approach outlined above, the third prong of the plain error test, i.e., whether the plain error affected substantial rights, is also satisfied. More specifically, the very real possibility that the district court in this case may have imposed a lower sentence under an advisory Guideline regime, combined with the near-impossibility of Gonzalez-Huerta demonstrating on the existing record that the district court likely would have done so, allows us to presume that Gonzalez-Huerta “was prejudiced by the imposition of a sentence under the mandatory Guidelines.” Barnett, 398 F.3d at 529. Further, there is nothing in the record that would rebut this presumption.9
That leaves the fourth prong of the plain error test. Under that prong, we must exercise our discretion to “correct a plain forfeited error affecting substantial rights if the error ‘seriously affect[s] the fairness, integrity or public reputation of judicial proceedings.’” Olano, 507 U.S. at 736, 113 S.Ct. 1770 (quoting United States v. Atkinson, 297 U.S. 157, 160, 56 S.Ct. 391, 80 L.Ed. 555 (1936)). The question is whether that standard is satisfied here, where there is a reasonable probability that, had the district court applied the Guidelines in an advisory rather than mandatory fashion, Gonzalez-Huerta would have received a lesser sentence than the one actually imposed.
In United States v. Brown, 316 F.3d 1151, 1161 (10th Cir.2003), we noted that the federal circuit courts “have not hesitated to exercise their discretion to correct” plain errors arising from sentencing where the “correct application of the sentencing laws would likely significantly reduce the length of the sentence.” Although we did not quantify what would constitute a “significant reduction” in the length of a sentence, a review of relevant case law suggests that almost any reduction in the amount of actual incarceration is sufficient to meet this definition. E.g., Glover v. United States, 531 U.S. 198, 203, 121 S.Ct. 696, 148 L.Ed.2d 604 (2001) (concluding, in context of appeal from denial of 28 U.S.C. § 2255 motion, “that any amount of actual jail time” resulting from district court’s misapplication of the Guidelines “has ... significance” for purposes of assessing prejudice); United States v. Villegas, 404 F.3d 355, 365, No. 03-21220, 2005 WL 627963, at *7 (5th Cir.2005) (concluding that, because district court’s error increased Guideline-suggested sentence by at least five months, the error seriously affected the fairness, integrity, or public reputation of judicial proceedings); United States v. Syme, 276 F.3d 131, 157-58 (3d Cir.2002) (reaching similar conclusion where district court’s error increased defendant’s minimum guideline sentence by seven months); see also Paladino, 401 *758F.3d 471, 482-83 (“It is a miscarriage of justice to give a person an illegal sentence that increases his punishment”); United States v. Smith, 267 F.3d 1154, 1160 (D.C.Cir.2001) (“we have no trouble concluding that a misapplication of the burden of proof that results in a defendant serving a longer sentence adversely affects the fairness and integrity of-the judicial proceeding.”); United States v. Martinez-Rios, 143 F.3d 662, 678 (2d Cir.1998) (“one would be hard-pressed to think of a more senseless injustice than the deprivation of a citizen’s liberty for several months as a result of [an] ... error.”); cf. United States v. Phipps, 319 F.3d 177, 192 (5th Cir.2003) (refusing to correct plain error where the erroneously long .sentence ran concurrently with a valid longer sentence); Brown, 316 F.3d at 1162. (refusing to correct plain error that likely operated in defendant’s favor).
Because of the nature of the error at issue here, it is impossible to quantify precisely how much Gonzalez-Huerta’s sentence might have been reduced-had the district court applied the Guidelines in an advisory fashion. That is because, as already discussed, the error affected the entire legal framework applied by the district court and counsel when Gonzalez-Huerta was sentenced, and thus the record on .appeal is simply not adequate to allow us to reasonably estimate what sentence the district court would likely have imposed had it applied the Guidelines in an advisory fashion. That said, it is not at all unreasonable to assume, particularly in light of the fact that Gonzalez-Huerta was sentenced at the very bottom of the applicable Guideline range, that, had the district court decided to exercise its discretion and deviate from the suggested Guideline range, it might have done so by imposing a sentence equivalent to that which would have been imposed under the next-lower Guideline range (51-63 months rather than 57-71 months). Doing so could conceivably have resulted in a reduction in Gonzalezr-Huerta’s sentence of up to six months. Under clearly established precedent, that potential reduction is serious enough to affect the “fairness, integrity or public reputation of judicial proceedings.” See, e.g., United States v. Knight, 266 F.3d 203, 207 (3d Cir.2001) (“application of an incorrect guideline range resulting in a sentence that is also within the correct range affects substantial rights”); United States v. Osuna, 189 F.3d 1289, 1294 (10th Cir.1999) (ordering resentenc-ing in plain error case where, absent district court’s sentencing error, defendant’s guideline range would have been 46-57 months rather than 51-63 months); United States v. Weaver, 161 F.3d 528, 530 (8th Cir.1998) (rejecting government’s assertion that “error did not affect [defendant’s] substantial rights because ... sentence he received fell within the Guidelines range ... which would have applied absent the error”); United States v. Spears, 159 F.3d 1081, 1088 (7th Cir.1998) (remanding where juvenile offenses were wrongly included, resulting in wrong criminal history category: “[t]he district court looked at the wrong sentencing range when determining [defendant’s] sentence. We have determined this to constitute plain error.”); United States v. Martinez-Rios, 143 F.3d 662, 675-76 (2d Cir.1998) (concluding that, although it was unclear whether correcting error would have any effect on sentencing level, remand was required under plain error analysis); United States v. Ford, 88 F.3d 1350, 1356 (4th Cir.1996) (holding that where district court miscalculated criminal history points “[t]he error clearly affected [defendant’s] substantial rights because the extra points caused [defendant] to be sentenced at a more severe guideline range”); United States v. Cabral-Castillo, 35 F.3d 182, 182 *759(5th Cir.1994) (remanding sentence where defendant was sentenced under a mistaken range of between 188 and 255 months even though defendant’s actual sentence, 188 months, fell within the proper range of 151 to 188 months); United States v. Robinson, 20 F.3d 270, 273 (7th Cir.1994) (“A sentence based on an incorrect guideline range constitutes an error affecting substantial rights and thus constitutes plain error.”); United States v. Plaza-Garcia, 914 F.2d 345, 347-48 (1st Cir.1990) (remanding sentence within both erroneously-applied and correct Guideline ranges under plain error doctrine because sentence “may well have been influenced by the [erroneous] sentencing recommendation”).
Even putting aside any estimates of how much Gonzalez-Huerta’s sentence could reasonably have been reduced, I agree with the Sixth Circuit that the revolutionary nature of Booker’s remedial holding, standing alone, warrants the exercise of our discretion in cases like Gonzalez-Huerta’s. More specifically, I conclude “it would be fundamentally unfair to allow [Gonzalez-Huerta’s] sentence, imposed under a mandatory Guidelines regime, to stand in light of this substantial development in, and alteration of, the applicable legal framework.” Barnett, 398 F.3d at 530; see Crosby, 397 F.3d at 115 (“[A] sentence unreasonable for legal error in the method of its selection is cause for concern because, in many cases, it will be impossible to tell whether the judge would have imposed the same sentence had the judge not felt compelled to impose a Guidelines sentence.”).
Although the majority concludes that Gonzalez-Huerta has failed to satisfy the fourth prong of the plain error test, there are, in my view, at least five flaws in the majority’s reasoning.10 First, the majority all but ignores our prior precedent, and that of other circuits, recognizing that forfeited sentencing errors (including simple misapplications of Guideline provisions) can, and often do, affect the fairness, integrity, or public reputation of judicial proceedings. Second, and relatedly, the majority fails (yet again) to acknowledge the dramatic change in sentencing law wrought by Booker, and instead suggests that the district court’s “mandatory application of the Guidelines [was not] particularly egregious.” Maj. Op. at 738. Were that characterization correct, I strongly suspect the Supreme Court would not now be vacating the judgments in the hundreds of criminal cases that were pending before it on direct review at the time of Booker’s issuance. Moreover, had the Supreme Court been in agreement with that characterization, it could easily have said so in Booker’s remedial holding, and thereby obviated the circuit-by-circuit wrangling that is now occurring over application of the plain error test to non-constitutional Booker errors. Third, by suggesting that a sentence imposed within the Guidelines does not implicate the fairness, integrity, or public reputation of judicial proceedings, the majority fails to give full effect to Booker’s remedial opinion, and instead demonstrates a preference for the pre-Booker, mandatory Guideline regime. We should judge the fairness, integrity, and reputation concerns not by whether the sentence was imposed under long-standing guidelines, but rather whether the sentence imposed satisfies those same concerns when reviewed under the changed *760law. Fourth, by suggesting that Gonzalez-Huerta cannot satisfy the fourth prong because his sentence was imposed within the Guidelines, the majority effectively usurps the function of discretionary sentencing that has been afforded to district courts by Booker. In other words, the majority refuses to afford the district court in this case an opportunity to exercise its discretion to sentence Gonzalezr-Huerta simply because, in the majority’s view, the Guideline sentence originally imposed is reasonable. The impropriety of this approach was succinctly outlined by the Fourth Circuit in United States v. Hughes, 401 F.3d 540, 556 n. 14 (4th Cir.2005):
It is not enough for us to say that the sentence imposed by the district court is reasonable irrespective of the error. The determination of reasonableness depends not only on an evaluation of the actual sentence imposed but also the method employed in determining it. Moreover, declining to notice the error would be tantamount to performing the sentencing function ourselves. This is so because the district court was never called upon to impose a sentence under an advisory guideline regime. That the particular sentence imposed here might be reasonable is not to say that the district court, now vested with broader sentencing discretion, could not have imposed a different sentence that might also have been reasonable. We simply do not know how the district court would have sentenced [defendant] had it been operating under the remedial scheme announced in Booker.
Fifth, although the majority suggests that granting relief to Gonzalez-Huerta would call into question the “tens of thousands [of] federal sentences” imposed under the Guidelines since their implementation, there is no indication in Booker that it was meant to be applied retroactively, and at least two circuits have expressly so held. See Humphress v. United States, 398 F.3d 855, 857 (6th Cir.2005) (holding that Booker does not apply retroactively to initial § 2255 motions); McReynolds v. United States, 397 F.3d 479, 481 (7th Cir.2005) (same); see also United States v. Price, 400 F.3d 844 (10th Cir.2005) (holding that Blakely does not apply retroactively); Bey v. United States, 399 F.3d 1266, 1269 (10th Cir. Mar.1, 2005) (holding that Booker could not be raised in a second or successive § 2255 motion). Moreover, in the name of allegedly preserving the integrity of established sentences, the majority effectively “condemn[s]” perhaps as many as one out of every seven defendants in the plain-error “set” of cases, including possibly Gonzalez-Huerta, “to serve an illegal sentence,” i.e., a sentence longer than that which would have been imposed by the district court under an advisory Guideline regime. Paladino, 401 F.3d 471, 484-85.
I cannot agree with my colleagues who conclude that a remand for resentencing in this case “would not advance fairness or the integrity of judicial proceedings” but “would more likely injure the reputation of the courts than improve it.” Hartz Concurrence, at 1. Specifically, the concern is voiced that remanding cases like Gonzalez-Huerta’s for resentencing under an advisory guideline regime “would serve only to permit the district court to deviate from th[e] guidelines in the exercise of an idiosyncratic personal view of fairness,” and thus would result in less uniform sentences. Id. I submit these concerns run counter to the mandate set forth in Booker, i.e., to afford defendants, including those whose appeals were pending on direct review at the time of Booker’s issuance, the opportunity of having the sentencing judge exercise his or her discretion under an advisory guideline regime, subject to appellate review for abuse of that discretion under a “reasonableness” stan*761dard. Does it advance the fairness, integrity, or public reputation of the courts if we ignore the Booker mandate and remove from the district court the very sentencing discretion the Supreme Court gave it? That a resulting sentence on remand may be less “uniform” and may deviate from the prior guideline sentence are not valid reasons for concluding the plain error we all agree occurred at sentencing should not. be corrected. To the contrary, the fact that the sentencing judge may impose a different sentence on remand is an argument for, rather than against, sentencing remand.
Because all four prongs of the plain error test are satisfied in this case, I would remand to the district court for resentenc-ing.
. Section 3742(e) sets forth standards of review on appeal, including de novo review of departures from the applicable Guidelines range.
. I agree with the majority that the error asserted by Gonzalez-Huerta is neither constitutional nor structural in nature.
. In United States v. Labastida-Segura, 396 F.3d 1140, 1142-43 (10th Cir.2005), this *751court applied the harmless error standard to a defendant who, like Gonzalez-Huerta, asserted a non-constitutional Booker error. The only difference is that the defendant in La-bastida-Segura was sentenced after Blakely and thus was able to assert a Blakely-based challenge to the Guidelines. Id. at 1142. Notably, however, the defendant in Labastida-Segura did not accurately predict the remedy that would ultimately be adopted by the Supreme Court in Booker, i.e., he did not object before the district court by asserting the Guidelines should be applied in an advisory rather than mandatory fashion. Instead, he asserted that the unconstitutional provisions of the Guidelines were not severable. Id. Nevertheless, this court treated the non-constitutional Booker error as if it had been raised below, applied the harmless error standard, and remanded the case for resentenc-ing. Id. at 1143.
Although it is unclear at this point, perhaps this court, given, the holding in Labastida-Segura, will adopt an approach similar to that recently announced by the First Circuit, i.e., "offering] to treat almost any colorable claim in the district court as preserving the Boolcer issue and avoiding plain error requirements.” United States v. Heldeman, 402 F.3d 220, 224, 2005 WL 708397, at *3 (1st Cir.2005).
. For example, in his supplemental appellate brief, Gonzalez-Huerta argues that "[u]nder the old [mandatory guideline] scheme, ... the [district] court was not allowed to consider that some jurisdictions have a ‘Fast Track’ program for illegal reentry defendants that allows them to receive substantially lower sentences than are available to defendants in jurisdictions without such a program.” Aplt. Suppl Br. at 10 (citing United States v. Armenta-Castro, 227 F.3d 1255, 1257 (10th Cir.2000)). Under the post-Booker advisory guideline scheme, however, he notes that “a sentencing court is required to consider 'the need to avoid unwarranted sentencing disparities among defendants with similar records who have been found guilty of similar conduct,’ " and thus it would be reasonable for the district court in this case on remand to “reduce the disparity produced by 'Fast Track' sentencing programs by lowering” his sentence since he "did not have the opportunity to benefit from such a program.” Id.
. The majority states that "structural errors must, at a minimum, be constitutional errors.” Maj. Op. at 734. Although the Supreme Court has sometimes used language suggesting that only constitutional errors can qualify as "structural errors,” e.g., Neder v. United States, 527 U.S. 1, 14, 119 S.Ct. 1827, 144 L.Ed.2d 35 (1999) ("Under our cases, a constitutional error is either structural or it is not.”), the Fourth Circuit has expressly held that non-constitutional errors can also qualify as structural errors. See United States v. Curbelo, 343 F.3d 273, 280 (4th Cir.2003) (holding, in a 2-1 decision, that, “whether violative of the Constitution or not, the error here is structural, and such errors 'invalidate the conviction’ without any showing of prejudice.”). Likewise, the Third Circuit and this court have suggested as much. See United States v. Stevens, 223 F.3d 239, 244 (3d Cir.2000) (stating that nonconstitutional errors "generally cannot amount to a structural defect”); United States v. Lewis, 21 Fed. Appx. 843 (10th Cir.2001) (unpublished decision) (concluding that non-constitutional errors can warrant automatic reversal) (implying, without directly concluding, that a violation of Fed.R.Crim.P. 8(c) was a structural error). Even assuming, arguendo, that structural errors can include non-constitutional errors, I would still conclude that the error asserted by Gonzalez-Huerta is not structural in nature.
. Notably, the percentage of post -Booker sentences falling below the advisory Guideline range for reasons other than a government-sponsored reduction has been steadily rising since the issuance of Booker. See Linda D. Maxfield, U.S. Sentencing Comm’n, Bata Extract on March 3: Numbers on Post-Booker Sentencings (Mar. 14, 2005) (available at http://www.ussc.gov/Blakely/booker— 030305.pdf) (noting that, as of March 3, 2005, 13.0 percent of all post -Booker sentences were below the guideline range for reasons other than a government-sponsored downward departure); Linda D. Maxfield, U.S. Sentencing Comm’n, Numbers on Post-Booker Sentenc-ings (Feb. 28, 2005) (noting that, as of February 17, 2005, 12.0 percent of all -post-Booker sentences were below the guideline range for reasons other than a government-sponsored downward departure).
. Support for the doctrine can also be drawn from O'Connor, where the Supreme Court held that an Ohio state defendant's "failure to object to a practice which Ohio had long allowed [could not] strip him of his right to attack the practice following its invalidation” by the Supreme Court during the pendency of his direct appeal. 385 U.S. at 93, 87 S.Ct. 252.
. Every circuit that has applied a plain error analysis to a Booker error has agreed that the first and second prongs of the test are satisfied. The government in this case likewise agrees that the first and second prongs of the test are satisfied.
. Like the Sixth Circuit in Barnett, I do not "discount the possibility ... that in other cases the evidence in the record will be sufficient to rebut the presumption of prejudice.” 398 F.3d at 529. Here, however, I am not aware of any "clear and specific” evidence in the record indicating that the district court would not have imposed a lower sentence under an advisory guideline regime. Id.
. The majority suggests that "several courts of appeals have collapsed the third and fourth prong analyses.” Maj. Op. at 736. I disagree. In my view, the circuits that have found plain error in light of Booker simply subscribe to the position that "[i]t is a miscarriage of justice to give a person an illegal sentence that increases his punishment...." Paladino, 401 F.3d at 482-83.