BOYCE F. MARTIN, JR., J., delivered the opinion of the court. GWIN, D.J. (pp. 531-34), delivered a separate concurring opinion. BOGGS, C.J. (pp. 534-39), delivered a separate opinion concurring in part and dissenting in part.
BOYCE F. MARTIN, JR., Circuit Judge.Yervin K. Barnett appeals his conviction and sentence for being a felon in possession of a firearm in violation of 18 U.S.C. § 922(g). For the following reasons, we AFFIRM Barnett’s conviction. However, we VACATE the sentence of the district court and REMAND for resentencing consistent with the Supreme Court’s decision in United States v. Booker, — U.S.-, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005).
I.
In the early morning hours of July 4, 2002, Officer Corey Jefferson of the Memphis Police Department responded to a burglary call at 661 Shel Lane. When Jefferson arrived at the address, he flashed his spotlight at the residence and observed a black male kneeling in front of a window with a long black object in his hand (al*519though Jefferson initially testified that he may have seen the suspect climbing out of the window). The suspect, upon seeing Jefferson, threw the object down and ran to a nearby car and drove away. Officer Jefferson gave pursuit. Jefferson testified that the object in the suspect’s hand looked like a shotgun, but he was not sure. He further testified that he was able to get “a pretty good look” at the suspect as he ran toward the car. During the pursuit, the suspect lost control of his car on a curve and ran over a curb and into a house. He then began to flee on foot. Jefferson pursued the suspect on foot for a short period of time, until Jefferson was unable to jump a fence and lost sight of the suspect. Jefferson then radioed to other officers the location where he last saw the suspect and returned to his squad car in an effort to form a perimeter around the area.
Within ten minutes, Officer Jane Martin, a member of the department’s canine unit, arrived on the scene and began searching the area. Martin’s dog apparently followed a trail to a shed where Yervin Barnett was hiding. Martin took Barnett into custody. Jefferson testified that upon seeing Barnett detained, he was able to recognize Barnett as the same individual he observed at 661 Shel Lane earlier that evening crouched in front of the window with the long dark object in his hand. While Barnett was in custody at the scene, he apparently told the officers that he was not acting alone that night. In response, Jefferson testified that he told Barnett that he was the only one he saw at the scene.
Officer Tina Crowe testified that she responded to 661 Shel Lane to perform a crime scene investigation on July 4, 2002. During her investigation, she recovered a black and chrome rifle from the front yard of that address. At trial, Jefferson testified that the recovered gun featured in a picture (exhibit two) was the long black object that he saw the suspect holding in his hand.
The only witness called by the defense was Janice Bell. Bell testified that she was with Barnett on the evening of July 3 until around 11:00 p.m. or 12:00 a.m., and that Barnett had left in the presence of another man, James Molist, who subsequently died before trial.
At trial, the district court instructed the jury on the applicable law regarding possession of a firearm by a felon under 18 U.S.C. § 922(g). The court instructed:
You should find that the Defendant had possession of the firearm, if he had control of it, even though it was not physically in his possession. But, it is not enough that the Defendant may have known about the firearm. A defendant possess [sic] a firearm only if he had control of it either alone or together with someone else. Next, I will talk about actual and constructive possession. Next, I want to explain something further about possession. The government does not necessarily have to prove that the Defendant physically possessed the firearm for you to find him guilty of this crime.
The law recognizes two kinds of possession, actual possession and constructive possession. Either one of these, if proved by the Government, is enough to convict. To establish actual possession, the Government must prove that the Defendant had direct and physical control over the firearm and knew that he had control of it. To establish constructive possession, the Government must prove that the Defendant had the right to exercise physical control over the firearm and knew that he had this right. And that he intended to exercise physical control over it at sometime either *520directly or through other persons. For example, if you left something with a friend intending to come back later to pick it up or intending to send someone else to come and pick it up for you, you would have constructive possession of that thing, while it was in the actual possession of your friend. But, understand that just being present where something is located does not equal possession. The Government must prove that the Defendant had actual or constructive possession of the firearm and knew that he did ....
Counsel for Barnett stated in closing argument:
We all know that people do burglaries when they are accompanied by other people. It could happen, right. We all know that every time a burglary happens, it is not just one person. It could be another person.... We also heard the statements made by Mr. Barnett given to Officer Jefferson. What did he tell you? Did you all catch anybody else? ... Maybe, there was somebody else. Maybe there was. What did Officer Jefferson say? He didn’t look for another person. Well, yes. I guess that there could have been somebody else
You heard the testimony of Janice Bell. Janice Bell said, that Mr. Barnett was accompanied by another man. His name was James Molist. And I submitted his death certificate in this case. At 11:00 at night, 11:00 or 12:00 o’clock at night, that’s pretty late. You remember the burglary happened about around 4:00, just a few hours later. I submit to you, that it is possible, that Mr. Molist was with Mr. Barnett that night. And that was possibly the other person.
In rebuttal closing, counsel for the United States stated:
So, if you conspire with someone else to go and kick in the front door of a citizen’s home, and invade that home, and take property from that home, without the permission of the homeowner or either you or your partner decide to grab a rifle from the home, then, both of you, under the law, have exercised control over it.
The defense objected and the district court sustained the objection to the use of the word “conspiracy,” as there was no conspiracy charge in the case. The court instructed the jury to disregard anything the prosecutor said about conspiracy and that line of argument. Counsel for the United States did not use the word “conspiracy” again in commenting on the defense theory of the case.
Returning to his closing, counsel for the United States again argued: “If you and Mr. Molist, the Defendant and Mr. Molist, went to the home and broke into the home; and let’s say that, it was Mr. Molist, who had the gun, the Defendant is still responsible.” Counsel for Barnett again objected. In a side bar, the court responded to the government’s argument: “Those are facts, that are not in evidence. There is no evidence, anything in the record.... [D]o we know that these were the two that did that? You didn’t argue that on Direct.” During the course of this bench conference, counsel for Barnett admitted that he had argued the theory that Molist, rather than Barnett, had been in possession of the firearm at the time of the apparent burglary. With the court’s permission, counsel for the United States continued his closing by responding to the defense’s argument as follows: “Just, hypothetically, if two people broke into a home, and one of them possessed the gun, and then under this law, as the Judge has read it to you, both can be charged with possession of it. Because if your partner *521exercises control and possession, controlling possession, hypothetically, then, you do as well, under the law, as has been instructed to you by Her Honor.”
On November 6; 2003, the jury convicted Barnett of being a felon in possession of a firearm in violation of 18 U.S.C. § 922(g). At the sentencing hearing on February 25, 2004, the district court calculated Barnett’s base offense level under the United States Sentencing Guidelines for “felon in possession of a firearm” to be 24 under section 2K2.1, but then added 2 points for his possession of a stolen firearm under section 2K2.1(b)(4), and 2 more points for reckless endangerment during flight under section 3C1.2. This yielded an adjusted offense level of 28. However, because Barnett had been convicted of at least three aggravated or violent felonies in the past, the district court was required to sentence him as an armed career criminal, which increased his offense level to 33 under section 4B1.4 of the Guidelines and imposed a statutory mandatory minimum of 180 months of imprisonment, see 18 U.S.C. § 924(e). With a criminal history category of VI, and an offense level of 33, the Guidelines required the district court to sentence Barnett within the Guidelines range of 235-292 months of imprisonment. Counsel for the United States requested sentencing in the upper end of the range, while Barnett requested a sentence in the low end. In sentencing Barnett to 265 months of imprisonment, in the middle of the range, the court stated:
Mr. Barnett, in this case, while this is a firearms case, looking back at your criminal history, there are five aggravated burglary convictions in your past. Those are very serious matters. The jury found you guilty of this offense. You are a career offender. The court finds that the low end of the guideline is not appropriate in this case. The court is going to sentence you to 265 months on this matter.... But that is going to be the court’s sentence, that is a sentence a little bit over 22 years, and I believe that that is appropriate under the totality of the circumstances in this case, that is going to be the court’s sentence, Mr. Barnett.
There was no objection to the district court’s calculations of the appropriate Guidelines range at the sentencing hearing.
II.
On appeal, Barnett seeks reversal of his conviction, alleging insufficiency of the evidence and prosecutorial misconduct. He also seeks remand for resentencing in light of the Supreme Court’s recent decision in United States v. Booker. We first consider the appeal of Barnett’s conviction and then address whether his sentence should be vacated and remanded for resentencing.
A.
Barnett’s first argument on appeal is that the evidence submitted at trial was constitutionally insufficient to sustain the jury’s verdict finding him guilty of being a felon in possession of a firearm in violation of 18 U.S.C. § 922(g). Barnett claims that the only witness who testified that he had actually seen Barnett with the gun was Officer Jefferson who, according to Barnett, testified inconsistently “throughout the course of the trial.” Because of these “inconsistences,” Barnett argues that “no reasonable juror could have believed Officer Jefferson,” and, therefore, there is insufficient evidence to sustain the jury’s verdict.
When a conviction is attacked for insufficiency of the evidence, the evidence is viewed in the light most favorable to the prosecution to determine whether any rational trier of fact could have found each *522essential element of the offense beyond a reasonable doubt. Hilliard v. United States, 157 F.3d 444, 447 (6th Cir.1998). This Court reverses a judgment for insufficiency of the evidence “only if [the] judgment is not supported by substantial and competent evidence upon the record as a whole.” United States v. Stone, 748 F.2d 361, 363 (6th Cir.1984). “Circumstantial evidence alone is sufficient to sustain a conviction and such evidence need not remove every reasonable hypothesis except that of guilt.” United States v. Spearman, 186 F.3d 743, 745 (6th Cir.1999).
We are convinced that Barnett’s conviction was based on “substantial and competent evidence.” Officer Jefferson testified at trial that he saw Barnett crouched outside the residence at 661 Shel Lane, holding a long black object that looked like a shotgun. He further testified that he saw Barnett throw the object to the ground as Barnett began to flee from the residence. Furthermore, Officer Crowe testified that upon investigating the residence after Barnett was apprehended, she found a black and chrome rifle in the front yard. This evidence is sufficient evidence to support the jury’s guilty verdict.
Barnett claims that because Officer Jefferson’s testimony was, in his view, inconsistent and unreliable, the government did not present sufficient evidence to sustain the guilty verdict. We disagree. This Court has consistently stated that “[i]n cases in which we assess the sufficiency of the evidence, we do not weigh the evidence, assess the credibility of the witnesses, or substitute our judgment for that of the jury.” United States v. Wright, 16 F.3d 1429, 1440 (6th Cir.1994) (citing United States v. Evans, 883 F.2d 496, 501 (6th Cir.1989)). Barnett makes no substantive argument that the evidence submitted to the jury was insufficient; rather, he merely argues that Jefferson cannot be believed. Consequently, we find that Barnett’s argument “is merely a challenge to [the witness’s] credibility, packaged as an insufficiency of the evidence claim.” United States v. Talley, 164 F.3d 989, 996 (6th Cir.1999). Thus, because “attacks on witness credibility are simply challenges to the quality of the government’s evidence and not to the sufficiency of the evidence,” United States v. Adamo, 742 F.2d 927, 935 (6th Cir.1984) (emphasis in original), Barnett’s challenge to his conviction on this ground must fail.
B.
Barnett also seeks reversal of his conviction based on the prosecutor’s closing argument at trial, which, according to Barnett, included misstatements of the law and consequently amounted to prosecutorial misconduct. Allegations of prosecutorial misconduct contain mixed questions of law and fact that this Court reviews de novo. United States v. Green, 305 F.3d 422, 429 (6th Cir.2002). In reviewing allegations of prosecutorial misconduct, this Court conducts a two-step inquiry. United States v. Francis, 170 F.3d 546, 549 (6th Cir.1999). First, we determine if the statements were improper. Id. If they were improper, we consider the following factors to determine if the comments were flagrant enough to warrant reversal: (1) whether the prosecutor’s remarks or conduct tended to mislead the jury or prejudice the accused; (2) whether the remarks were isolated or extensive; (3) whether the remarks were accidentally or deliberately made; and (4) the overall strength of the evidence against the accused. Id.
We begin, and end, our analysis of Barnett’s prosecutorial misconduct claim by considering whether the prosecutor’s closing argument was improper. In determining whether it was improper, we “view the conduct at issue within the context of the *523trial as a whole.” United States v. Beverly, 369 F.3d 516, 543 (6th Cir.2004) (citing United States v. Young, 470 U.S. 1, 12, 105 S.Ct. 1038, 84 L.Ed.2d 1 (1985)). When reviewing the conduct at issue, “[i]t is also appropriate to consider whether, and to what extent, a prosecutor’s improper argument is invited by defense counsel’s statements.” United States v. Jacobs, 244 F.3d 503, 508 (6th Cir.2001) (citing United States v. Hickey, 917 F.2d 901, 905 (6th Cir.1990)).
In this case, the alleged prosecutorial misconduct involves the prosecutor’s “continued insistence during rebuttal to instruct the jury on the law of conspiracy.” In closing argument, counsel for the Untied States said that “if you conspire with someone else to ... invade [a] home, or either you or your partner decide to grab a rifle from the home, then both you of under the law have exercised control over it.” The district court sustained Barnett’s objection to the use of the word “conspiracy,” and instructed the jury to disregard the government’s arguments regarding conspiracy on the ground that it was not an element of the charge. The prosecutor then continued, essentially saying the same thing, but without using the word “conspiracy.” Counsel for Barnett again objected, although in a side bar he admitted that the prosecutor was merely responding to defense counsel’s argument that someone other than Barnett could have been holding the gun. Upon hearing that, the court allowed the prosecution to make its argument using the hypothetical quoted above.
We find that the prosecutor did not engage in misconduct. The prosecutor only mentioned “conspiracy” once in closing argument. The court, however, sustained Barnett’s objection to the use of the word “conspiracy” and expressly admonished the jury regarding this statement, instructing them to disregard “anything [the prosecutor] said about conspiracy.” This cured any possible impropriety of the prosecutor’s use of the word “conspiracy.” See United States v. Monus, 128 F.3d 376, 394 (6th Cir.1997). The subsequent statements, none of which used the word “conspiracy,” were not improper. They simply responded to Barnett’s theory of the case — namely, that someone other than Barnett had possession of the gun. Barnett points to no case law suggesting that the government’s statements — legitimately responding to the defense’s theory during closing arguments — were improper. In fact, this Court has held that rebuttal statements that similarly respond to a defendant’s closing argument are not prose-cutorial misconduct. See, e.g., Jacobs, 244 at 508 (holding that 'a prosecutor did not commit misconduct since defense counsel “opened the door” to prosecution rebuttal by arguing facts not in the record); Monus, 128 F.3d at 394 (holding that a prosecutor’s hypothetical questions to the jury in response to defense argument were proper).
While Barnett claims that the prosecutor’s statements were legally incorrect, he fails to provide support forbhis proposition. It is well-established that actual or constructive possession of a firearm is sufficient to give rise to liability under section 922(g). See, e.g., United States v. DeJohn, 368 F.3d 533, 545 (6th Cir.2004) (quoting United States v. Schreane, 331 F.3d 548, 560 (6th Cir.2003)). Thus, for the aforementioned reasons, we are convinced that the prosecutor’s closing argument does not constitute prosecutorial misconduct.
III.
While this case was pending on appeal before this Court, the Supreme Court issued its decision in United States v. Book*524er. The Court issued two opinions in Booker, one authored by Justice Stevens concerning the merits of the constitutional challenge, and the other authored by Justice Breyer addressing the necessary remedy for what the Court found to be a constitutional violation. In Justice Breyer’s opinion, the Court expressly severed and excised 18 U.S.C. § 3553(b)(1), which had required sentencing courts to impose a sentence within the applicable Sentencing Guidelines range, subject to departures in certain limited cases.. Booker, — U.S. at -, 125 S.Ct. at 765. Consequently, under Booker, the Sentencing Guidelines are now advisory in all cases, including those that do not involve a Sixth Amendment violation. Id. at 769. In so holding, the Court expressly stated that its “remedial interpretation of the Sentencing Act” must be applied “to all cases on direct review.” Id. The Booker Court made it clear that this remedial scheme should apply not only to those defendants whose sentences had been imposed in violation of the Sixth Amendment, but also to those defendants who had been sentenced under the mandatory Guidelines without suffering a Sixth Amendment violation. Id. at 765 (noting that while defendant Fanfan’s sentence did not violate the Sixth Amendment, the parties could seek resentencing under the new advisory regime); see United States v. Davis, 2005 WL 334370, at *8 (3d Cir. Feb.11, 2005) (remanding for resentencing under Booker despite absence of Sixth Amendment violation). Because this case was pending on direct review when Booker was decided, the holdings of Booker are applicable in the case at bar.
A.
Barnett first argues that the application of the Armed Career Criminal Act, 18 U.S.C. § 924(e), in this case violated the Sixth Amendment principles established in Apprendi v. New Jersey, 530 U.S. 466, 120 S.Ct. 2348, 147 L.Ed.2d 435 (2000), and reiterated in Blakely v. Washington, 542 U.S.-, 124 S.Ct. 2531, 159 L.Ed.2d 403 (2004), and Booker because the trial judge, rather than the jury, determined the nature of Barnett’s previous convictions. According to Barnett, the government was required to plead in the indictment “every fact ... used to increase [Barnett’s] sentence above the statutory maximum, ... [such as] whether or not the defendant’s prior convictions were for crimes of violence or [for] controlled substances offenses.”
Existing case law establishes that Apprendi does not require the nature or character of prior convictions to be determined by a jury. In Apprendi, the Supreme Court expressly excepted the fact of a prior conviction from the rule requiring issues of fact that increase a defendant’s penalty to be submitted to the jury. 530 U.S. at 490, 120 S.Ct. 2348. This Court, among others, has rejected the argument that Apprendi requires the nature of prior convictions to be determined by a jury, holding instead that the district court’s authority to determine the existence of prior convictions was broad enough to include determinations regarding the nature of those prior convictions. For example, in United States v. Becerra-Garcia, 28 Fed.Appx. 381, 2002 WL 22038, at *3-5 (6th Cir. Jan.2, 2002) (unpublished opinion), a panel of this Court held that a district court did not violate Apprendi’s Sixth Amendment holding by determining whether the defendant’s prior conviction was for an aggravated felony. In Becerra-Garcia, we cited a number of courts that have reached similar conclusions, such as the Eighth Circuit, which, in United States v. Campbell, 270 F.3d 702, 707-09 (8th Cir.2001), held that Apprendi does not require the nature of a defendant’s prior felony offenses as “violent felonies” or *525“serious drug offenses” under the Armed Career Criminal Act to be proved to a jury.
In the present case, Barnett, like the defendant in Campbell, claims that the failure of the district court to submit to the jury the question of the nature of his prior convictions under the Armed Career Criminal Act violated Apprendi. Given the case law establishing that Apprendi does not require the nature of prior convictions to be determined by a jury, we reject Barnett’s argument on this issue. Moreover, there is no language in Booker suggesting that the Supreme Court, as part of its remedial scheme adopted in that case, intended to alter the exception to Appren-di allowing district courts to consider the fact and nature of prior convictions without submitting those issues to the jury. Thus, for the foregoing reasons, we hold that there was no Sixth Amendment violation in the present ease.
B.
Barnett’s second argument is that given the Supreme Court’s decision in Booker making the Sentencing Guidelines advisory, this Court should vacate his sentence and remand the case for resentencing “in light of the fact that the district court judge was sentencing the defendant as if the guidelines were mandatory.” For the following reasons, we agree.
The parties conceded at oral argument that Barnett did not challenge his sentence on this or any other ground before the district court. Therefore, we review the district court’s decision for plain error. See Booker, — U.S. at ——, 125 S.Ct. at 769 (noting that whether a new sentencing hearing is required depends on “ordinary prudential doctrines,” such as “whether the issue was raised below and whether it fails the ‘plain-error’ test”). In reviewing for plain error, we must consider whether there was plain error that affects substantial rights and that, in, our discretionary view, seriously affects the fundamental fairness, integrity, or public reputation of judicial proceedings. Johnson v. United States, 520 U.S. 461, 466, 117 S.Ct. 1544, 137 L.Ed.2d 718 (1997) (citing United States v. Olano, 507 U.S. 725, 732, 113 S.Ct. 1770, 123 L.Ed.2d 508 (1993)).
1.
We first consider whether there was error under current law. United States v. Rogers, 118 F.3d 466, 471-72 (6th Cir.1997). In the instant case, Barnett was sentenced under the pre-Booker mandatory Sentencing Guidelines. The district court sentenced Barnett to 265 months of imprisonment followed by four years of supervised release, which fell within the Guidelines range of 235-292 months as required by 18 U.S.C. § 3553(b)(1). This sentencing procedure was correct at the time, but now, because section 3553(b)(1) has been excised and severed under Booker, the district court erred by treating the Guidelines as mandatory when it sentenced Barnett. Thus, the first requirement for finding plain error is satisfied in the present case.
2.
The next issue is whether the error was “plain.” In this context, “ ‘[p]lain’ is synonymous with ‘clear’ or, equivalently, ‘obvious.’ ” Olano, 507 U.S. at 733-34, 113 S.Ct. 1770. The Supreme Court has expressly held 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 an error be plain at the time of appellate consideration.” Johnson, 520 U.S. at 468, 117 S.Ct. 1544; accord United States v. Calloway, 116 F.3d 1129, 1136 (6th Cir.1997). In the present case, at the time Barnett was sentenced, the *526Sentencing Guidelines were mandatory and not, as they are now, advisory. Furthermore, controlling case law pre-Booker consistently -held that the Sentencing Guidelines were constitutional and mandatory even after the uncertainty occasioned by the Supreme Court’s decision in Blakely. See, e.g., United States v. Koch, 383 F.3d 436 (6th Cir.2004) (en banc), overruled by Booker, — U.S. at -, 125 S.Ct. at 769. Booker, however, effectuated a “clear” and “obvious” change in law by making the Sentencing Guidelines advisory. Given this change in the law, we hold that it was plain error for Barnett to be sentenced under a mandatory Guidelines regime that has now become advisory.
3.
Third, the defendant is required to demonstrate that the plain error “affect[ed] substantial rights.” Fed.R.Crim.P. 52(b); Olano, 507 U.S. at 734, 113 S.Ct. 1770. As the Supreme Court reiterated in United States v. Cotton, 535 U.S. 625, 632, 122 S.Ct. 1781, 152 L.Ed.2d 860 (2002) (quoting Olano, 507 U.S. at 734, 113 S.Ct. 1770) (emphasis added), the phrase “affect substantial rights” is generally synonymous with “prejudicial,” which “usually means that the error ‘must have affected the outcome of the district court proceedings.’ ” However, the Supreme Court has noted, and this Circuit has recognized, two exceptions to the requirement that the defendant demonstrate-that the-error “affected the outcome of the district court proceedings.” First, there is a class of so-called “structural” errors, which, the Supreme Court has instructed, “can be corrected regardless of their effect on the outcome.” Olano, 507 U.S. at 735, 113 S.Ct. 1770. “A ‘structural’ error is a ‘defect affecting the framework within which the trial proceeds, rather than simply an error in the- trial process itself.’ ” Johnson, 520 U.S. at 468, 117 S.Ct. 1544 (quoting Arizona v. Fulminante, 499 U.S. 279, 310, 111 S.Ct. 1246, 113 L.Ed.2d 302 (1991)). The Supreme Court has found “structural errors only in a very limited class of cases,” id., such as where a defendant is denied certain fundamental rights, including the right to a public trial, Waller v. Georgia, 467 U.S. 39, 104 S.Ct. 2210, 81 L.Ed.2d 31 (1984), the right to self-representation at trial, McKaskle v. Wiggins, 465 U.S. 168, 104 S.Ct. 944, 79 L.Ed.2d 122 (1984), and the right to counsel, Gideon v. Wainwright, 372 U.S. 335, 83 S.Ct. 792, 9 L.Ed.2d 799 (1963). In such cases, because the error was “structural,” the defendant was not required to demonstrate that he was prejudiced, or, in other words, that the error affected the outcome of the district court proceedings.
Second, the Supreme Court’s decision in Olano “made it quite clear that in some situations a presumption of prejudice is appropriate” if the defendant cannot make a specific showing of prejudice. Manning v. Huffman, 269 F.3d 720, 726 (6th Cir.2001) (holding that a presumption of prejudice was appropriate in a habeas case where an alternate juror participated in jury deliberations, even absent evidence that the error affected the jury’s deliberations and its verdict): United States v. Segines, 17 F.3d 847, 852 (6th Cir.1994) (noting that “[t]he Supreme Court has stopped short ... of establishing a blanket rule that shifts the burden of persuasion on the defendant in all cases.... [There also may be] ‘errors that should be presumed prejudicial if the defendant cannot make a specific showing of prejudice.’ ”) (quoting Olano, 507 U.S. at 735, 113 S.Ct. 1770).
Courts have presumed prejudice, and have thus found the third prong of plain error review satisfied, in cases where the inherent nature of the error made it excep*527tionally difficult for the defendant to demonstrate that the outcome of the lower court proceeding would have been different had the error not occurred. For instance, in United States v. Adams, 252 F.3d 276, 287 (3d Cir.2001), the Third Circuit found plain error where the defendant was not given the opportunity to exercise his right of allocution. In considering whether the defendant could show that the court’s error was prejudicial, the court expressly noted the difficulty in establishing that the allocution error affected the outcome of the district court proceedings. See id. (“In order to prove that the error actually ‘affected the outcome of the district court proceedings,’ [the defendant] would have to point to statements that he would have made at sentencing, and somehow show that these statements would have changed the sentence imposed by the District Court.”). Because of “the nature of the right and the difficulty of proving prejudice from its violation,” id. at 287, the court concluded that it would presume prejudice rather than require the defendant to make the “enormously difficult” showing that the error affected the district court’s sentencing decision, id. (quoting United States v. Alba Pagan, 33 F.3d 125, 130 (1st Cir.1994)) (internal quotation marks omitted). This Court reached a similar result in United States v. Riascos-Suarez, 73 F.3d 616, 627 (6th Cir.1996), where we remanded for resentencing because the defendant was not afforded the opportunity to alloeute and the error “could have had an effect on his sentence.” See also United States v. Cole, 27 F.3d 996, 999 (4th Cir.1994) (implicitly adopting presumption of prejudice in plain error context where a defendant was denied his right to alloeute and, thus, “may have been able to persuade the court” that a lower sentence was appropriate). The continued, validity of Olano’s category of “presumed prejudicial” errors was recently reaffirmed by the Fifth Circuit sitting en banc in United States v. Reyna, 358 F.3d 344, 351-52 (5th Cir.), cert. denied, — U.S.-, 124 S.Ct. 2390, 158 L.Ed.2d 966 (2004), where the court held that it would presume that a, ..defendant suffered prejudice from a court’s failure to allow him to allo-cute, despite the defendant’s inability to demonstrate how the error affected the sentence imposed by the district court.
In addition to the allocution context, courts have been willing to presume prejudice, both implicitly and explicitly, in plain error review of other types of errors that, by their nature, keep the party from being able to demonstrate that, in the absence of that error, the outcome of - his trial or sentence would have been different. For example, in United States v. Plaza-Garcia, 914 F.2d 345, 347-48 (1st Cir.1990), then-Chief Judge Stephen Breyer vacated a sentence that fell within both erroneously applied and correct Guideline ranges under the plain error doctrine because the sentence “may well have been influenced by the [erroneous] sentencing recommendation.” See also United States v. Syme, 276 F.3d 131, 153-55 (3d Cir.2002) (holding that even though a constructive amendment to an indictment does not constitute a “structural” error, it nevertheless must be “presumed prejudicial” in light of the difficulty of proving prejudice resulting from constructive amendments).
As established above, the plain error in the instant case is that the sentencing court failed to treat the Sentencing Guidelines as advisory in determining Barnett’s sentence. The record shows that the district court imposed- a sentence based on the assumption — which, again, was correct, at the time but, incorrect in light of Booker — that the Guidelines were mandatory. We are convinced that.this is an appropriate case in which to presume prejudice under the Supreme Court’s deci*528sion in Olano. First, if the district court in this case had not been bound by the range prescribed in the Guidelines, Barnett may have received a lower sentence. It is uncontested that the district court would have had the discretion, under the new advisory Guidelines regime, to impose a sentence as low as 180 months of imprisonment, the statutory minimum provided by the Armed Career Criminal Act, 18 U.S.C. § 924(e), which is significantly lower than the 265 months he received under the application of the mandatory Guidelines.
Second, it would be exceedingly difficult for a defendant, such as Barnett, to show that his sentence would have been different if the district court had sentenced him under the advisory, rather than the mandatory, Guidelines framework. This is true in part because of the fundamental alteration of the sentencing process brought about by Booker’s remedial holding. 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. This discretion was not present at the time Barnett was sentenced under the mandatory Guidelines. As the Second Circuit recently observed, it is “impossible to tell what considerations counsel for both sides might 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. Crosby, No. 03-1675, slip op. at 28-29 (2d Cir. Feb. 2, 2005). Under the new post-Booker framework, counsel are now able to present aggravating and mitigating circumstances “that existed at the time [of pr e-Booker sentencing] but were not available for consideration under the mandatory Guidelines regime.” Id. at 35.
This fundamental difference between the pre- and post-Booker sentencing frameworks illustrates our deep concern with speculating, based merely on a middle-of the-range sentence imposed under the mandatory Guidelines framework, that the district court would not have sentenced Barnett to a lower sentence under the advisory Guidelines regime. That the district court chose to sentence Barnett in the middle of that mandatory range does not necessarily suggest that the district' court would now feel that 265 months of imprisonment is the proper sentence for Barnett. Nor does it suggest that the court would not have sentenced Barnett to a lower sentence if it had the discretion, which it does now, to apply the Guidelines in an advisory fashion.
The extraordinary difficulty facing defendants such as Barnett in showing that the use of mandatory, rather than advisory, Guidelines affected the outcome of their sentencing proceedings is exacerbated by the fact that to make such a showing, the defendants would presumably have to demonstrate that the district court somehow intimated that it felt constrained by the Guidelines or that it would have preferred to sentence the defendant to a lower sentence. This, in our view, is too exacting a burden, given the fact that this Court, along with others, had repeatedly instructed sentencing courts pr e-Booker to impose sentences within the applicable mandatory Guidelines range, with limited exceptions, and had consistently upheld the constitutionality of the Guidelines and their mandatory nature, even after the Supreme Court’s decision in Blakely. See, e.g., Koch, 383 F.3d at 440 (noting that “our Circuit has consistently turned back Sixth Amendment challenges to Guideline enhancements so long as the resulting sentence falls below the congressionally-pre-scribed statutory maximum”), overruled by Booker, — U.S. at-, 125 S.Ct. at 769. *529This well-established case law substantially undermined any need or incentive for sentencing courts pr e-Booker to note their objections and reservations in sentencing defendants under the then-mandatory Guidelines. It would be improper for this Court now to require defendants such as Barnett, 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.
As the Fourth Circuit recently noted, in sentencing under the mandatory Guidelines, “the district court was never called upon to impose a sentence in the exercise of its discretion.... We simply do not know how the district court would have sentenced [the defendant] had it been operating under the regime established by Booker,” United States v. Hughes, 396 F.3d 374, at 381 n. 8, 2005 WL 147059, at *5 n. 8 (4th Cir. Jan. 24, 2005). Instead of speculating as to the district court’s intentions in the pr e-Booker world, and trying to apply those intentions to predict the same court’s sentence under the post-Booker scheme, we are convinced that the most prudent course of action in this case is to presume prejudice given the distinct possibility that the district court would have imposed a lower sentence under the new post -Booker framework and the onerous burden he would face in attempting to establish that the sentencing court would have imposed such a sentence.
This is not to discount the possibility, however, that in other cases the evidence in the record will be sufficient to rebut the presumption of prejudice. While “an appellate court will normally be unable to assess the significance of any [sentencing] error that might have been made,” Crosby, slip op. at 35, we can imagine cases where the trial record contains clear and specific evidence that the district court would not have, in any event, sentenced the defendant to a lower sentence under an advisory Guidelines regime. See Crosby, slip op. at 35 (noting that “an educated guess as to the likely outcome of a remand ... might be wrong, absent a dear indication at the original sentencing supporting the inference that the same sentence would have been imposed under the post-Booker/Fan-fan regime”) (emphasis added). This, however, is not one of those cases. While the dissent claims that there is “concrete,” “affirmative,” and “ample” evidence indicating that the district court would not give Barnett a lower sentence on remand under the post -Booker framework, the only evidence that' the dissent cites for this proposition is the district court’s middle-of-the-range' sentence imposed under the mandatory Guidelines regime. This, in our view, is insufficient to rebut the presumption that Barnett was prejudiced by the imposition of a sentence under the mandatory Guidelines.
In summary, because Barnett has demonstrated that he was sentenced under the Sentencing Guidelines as if- they were mandatory, rather than advisory, and because he has shown that the district court might have exercised its discretion to impose a lower sentence had it known that the Guidelines were advisory, we hold that Barnett’s substantial rights have been affected.
4.
“The final step in plain error analysis is to determine whether this case warrants the exercise of our discretion.” Rogers, 118 F.3d at 473. We correct plain errors affecting substantial rights in those cases where the error “seriously affect[s] the fairness, integrity or public reputation of judicial proceedings.” United States v. Atkinson, 297 U.S. 157, 160, 56 S.Ct. 391, 80 L.Ed. 555 (1936).
*530We conclude that an exercise of our discretion is appropriate in the present case. Barnett’s sentence was imposed under a framework that has now been substantially altered by Booker’s severing and excising of 18 U.S.C. § 3553(b)(1), the provision that made the Guidelines mandatory. In our view, it would be fundamentally unfair to allow Barnett’s sentence, imposed under a mandatory Guidelines regime, to stand in light of this substantial development in, and alteration of, the applicable legal framework. The better course, we believe, is to vacate Barnett’s sentence and remand for resentencing, thus affording the district court the opportunity to re-sentence him in the first instance. “We would be usurping the discretionary power granted to the district courts by Booker if we were to assume that the district court would have given [the defendant] the same sentence post-Booker.” United States v. Oliver, 397 F.3d 369, at 381 n. 3, 2005 WL 233779, at *8 n. 3 (6th Cir. Feb. 2, 2005); see Williams v. United States, 503 U.S. 193, 205, 112 S.Ct. 1112, 117 L.Ed.2d 341 (1992) (“[I]t is not the role of an appellate court to substitute its judgment for that of the sentencing court as to the appropriateness of a particular sentence.”) (quoting Solem v. Helm, 463 U.S. 277, 290 n. 16, 103 S.Ct. 3001, 77 L.Ed.2d 637 (1983)).
Furthermore, we decline to consider the reasonableness of Barnett’s sentence imposed under the Guidelines without first giving the district court the opportunity to re-sentence Barnett under the new post-Booker framework. As the Fourth Circuit recently stated:
In determining whether the exercise of our discretion is warranted, it is not enough for us to say that the sentence imposed by the district court is reasonable irrespective of error. The fact remains that a sentence has yet to be imposed under a regime in which the guidelines are treated as advisory. To leave standing this sentence simply because it may happen to fall within the range of reasonableness unquestionably impugns the fairness, integrity, or public reputation of judicial proceedings.... This is so because the district court was never called upon to impose a sentence in the exercise of its discretion. 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.
Hughes, 396 F.3d 374, 2005 WL 147059, at *5 n. 8; accord Crosby, slip op. at 28 (“Even if reasonable as to length, 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.”). Because we are convinced that sentencing Barnett under mandatory Guidelines “seriously affect[ed] the fairness, integrity [and] public reputation of judicial proceedings,” Atkinson, 297 U.S. at 160, 56 S.Ct. 391, now that we know those Guidelines are advisory, we exercise our discretion to notice the plain sentencing error in the present case and vacate Barnett’s sentence.
C.
We note briefly that because we have concluded that the district court committed plain error in this case, that error cannot constitute “harmless error.” An error may be harmless only where the government is able to prove that none of the defendant’s substantial rights has been affected by the error. See Fed.R.Crim.P. 52(a). Because this Court has determined that the error in this case affected Bar*531nett’s substantial rights, the government, therefore, is unable to establish that the error was harmless.
IV.
For the reasons stated herein, we AFFIRM Barnett’s conviction, but VACATE Barnett’s sentence and REMAND for re-sentencing consistent with this opinion and with the Supreme Court’s decision in Booker.