RUSSELL, District Judge.
Defendant-Appellant Bentley Vaught (“Vaught”) appeals from a sentence imposed pursuant to Vaught’s guilty plea for illegally possessing a firearm. Vaught challenges the district court’s (i) denial of a motion to recuse or disqualify; (ii) application of an attempted murder sentence enhancement; (iii) application of a four-level enhancement for obstruction of justice; (iv) upward departure based on Vaught’s criminal history and likelihood of recidivism; (v) imposition of a five-year term of supervised release; (vi) imposition of a special condition upon Vaught’s supervised release involving placement in a custodial mental health facility; and (vii) denial of Vaught’s right to allocute during the sentencing hearing.
BACKGROUND
The April 22, 2001 incident leading to Vaught’s arrest involved a dispute between Vaught and his sister, Carol Hollins, about the care of their elderly mother. Vaught entered the apartment where he and his mother lived and found Carol talking to their mother in the kitchen. The two argued, and Vaught pushed Carol into the kitchen table. He then threatened Carol, saying that if she ever put their mother into a nursing home, he would kill her. Carol left the apartment and went home; later that day, she received a frantic phone call from her mother warning her that Vaught was on the way to kill her and that [232]*232he had a gun. Carol left the house and called 911, after which a police officer escorted her back to her house so she could prepare to go to the police station. While she was inside the house, the officers saw Vaught drive by the house, stopped and searched him, and, after finding the handgun in his pocket along with 6-8 rounds of ammunition, arrested him.
On August 9, 2001, Vaught was indicted for violating 18 U.S.C. § 922(g)(1), which prohibits convicted felons from possessing firearms. On October 26, 2001, Vaught pled guilty to that charge before District Judge Trauger, to whom the case was assigned, without entering into a plea agreement. On February 7, 2002, Judge Trauger issued an order recusing herself and the case was reassigned to Judge Haynes. The sentencing hearing began on February 8, 2002 and was then continued until April 5, 2002. When the hearing recommenced, Vaught waived his right to be present in the courtroom until the district court was ready to impose the sentence. At this hearing, the district court heard testimony from government witnesses and informed the parties that it was considering an upward departure pursuant to USSG § 4A1.3. Judge Haynes then continued the sentencing hearing in order to give the parties the opportunity to prepare to argue the issue. In July 2002, Vaught filed a Motion for Disqualification requesting that a judge from outside the Middle District of Tennessee be assigned; the district court denied this motion without opinion.
The sentencing hearing resumed on June 13, 2003, and the parties presented their arguments about which guideline provision applied to the case. The district court applied USSG § 2A2.1(a)(l) (the guideline provision for attempted murder), which provided a base offense level of 28; the district court then departed downward three levels for acceptance of responsibility. Judge Haynes then added a two-level enhancement for each of two instances of witness intimidation pursuant to USSG § 3C1.1 and also departed upwards by two offense levels (for a total base level of 31) based on a finding that the offense level of 29 did not reflect Vaught’s likelihood of recidivism. The total offense level of 31, combined with Vaught’s criminal history category of I, yielded a sentencing range of 108-135 months; Judge Haynes sentenced the defendant to 108 months in prison to be immediately followed by five years of supervised release, with special conditions to include custodial arrangements at a mental health facility.
ANALYSIS
A. Motion for Disqualification
Vaught argues that the district court improperly denied his Motion for Disqualification of Judges from Middle District of Tennessee. We review a district court’s denial of a 28 U.S.C. § 455(a) motion to disqualify for abuse of discretion. United States v. Sammons, 918 F.2d 592, 599 (6th Cir.1990). Under that statute, a judge “shall disqualify himself in any proceeding in which his impartiality might reasonably be questioned.” 28 U.S.C. § 455(a). We have defined this to mean that “a judge must recuse himself if a reasonable, objective person, knowing all of the circumstances, would have questioned the judge’s impartiality.” Hughes v. United States, 899 F.2d 1495, 1501 (6th Cir.1990). Vaught based his motion to disqualify on the fact that John Hollins, Sr., husband of Vaught’s sister Carol, was a prominent attorney in the Nashville area, past president of the Nashville Bar Association, and a member of various other professional organizations. In United States v. Dandy, we held that a judge who was acquainted with a government witness [233]*233did not err by denying a motion for recusal. 998 F.2d 1344, 1349 (6th Cir.1993). Similarly, there is no evidence in this case that the judge’s acquaintance with John Hollins, no matter how long-standing, extended beyond that level in any way that requires recusal (i.e., that their relationship was personal or fiduciary). See also United States v. Lovaglia, 954 F.2d 811 (2nd Cir.1992) (holding recusal not required where case involved a family whom district judge had known personally seven or eight years earlier); United States v. Cole, 293 F.3d 153, 164 (4th Cir.2002) (holding no abuse of discretion where judge had personal relationship with government witnesses but had not had contact with them for over ten years).
B. Sentencing under USSG § 2A2.1 (Attempted Murder)
Vaught argues that the district court erred in sentencing him under the USSG for attempted murder. We review a district court’s application of the sentencing guidelines de novo. United States v. Hicks, 4 F.3d 1358, 1361 (6th Cir.1993). A district court’s factual findings, however, are reviewed for clear error. Rogers v. Howes, 144 F.3d 990, 992 (6th Cir.1998); United States v. Quigley, 382 F.3d 617, 621 (6th Cir.2004). Here, the district court sentenced the defendant under USSG § 2A2.1, the guideline for attempted murder, based on the Guidelines’ cross-reference provision, USSG § 2X1.1, which provides: “[w]hen attempt, solicitation, or conspiracy is expressly covered by another offense guideline section, apply that guideline section.” The district court applied USSG § 2K2.1(c)(l)(A), which directs the sentencing court as follows: “[i]f the defendant used or possessed any firearm or ammunition in connection with the commission or attempted commission of another offense ... with knowledge or intent that it would be used or possessed in connection with another offense, apply § 2X1.1 in respect to that other offense, if the resulting offense level is greater than that determined [under USSG § 2K1.1].” The United States need not charge and convict the defendant with the “other” offense; it need only prove the facts supporting the greater charge by a preponderance of the evidence. United States v. Watts, 519 U.S. 148, 156, 117 S.Ct. 633, 136 L.Ed.2d 554 (1997); United States v. Milton, 27 F.3d 203, 208-209 (6th Cir.1994). Even if the district judge does not make detailed findings as to these supporting facts, the Court of Appeals need not remand the case; we may look to the record to determine whether the district judge’s decision was clear error. United States v. Miller, 161 F.3d 977 (6th Cir.1998), citing United States v. Alexander, 59 F.3d 36, 39-40 (6th Cir.1995); United States v. Washington, 127 F.3d 510, 515 (6th Cir.1997), cert denied, 524 U.S. 940, 118 S.Ct. 2348, 141 L.Ed.2d 2718 (1998) (reviewing trial transcript to determine the defendant’s role in commission of the offense).
Vaught argues that the evidence before the district court did not support a finding of attempted murder. He asserts (i) that he was unable to form the specific intent required for murder and (ii) that his actions did not constitute the “substantial step” required for an attempt. As to the specific intent argument, Vaught argues that, although his intoxication was voluntary, it nevertheless provides a defense to the mens rea element of murder. In United States v. Neuman, we held that voluntary intoxication may sometimes defeat mens rea, but not where the defendant was “capable of rational thought and intentional behavior.” 889 F.2d 88, 92-3 (6th Cir.1989). Although the evidence indicated that Vaught had been drinking, that beer was found in his car at the time of the arrest, and that one of the arresting [234]*234officers observed him to be unsteady on his feet and slurring his speech, it also showed that he obtained the weapon, called his sister, drove to her house and decided not to turn into her driveway when he saw the police car parked there. The district court also heard evidence that Vaught told his mother that he intended to kill Carol, that he told two of his cell mates after his arrest that he had intended to kill her, and that he threatened violence against her in a December 2002 letter to her son. Based on this evidence, the district court’s determination that Vaught had the requisite mens rea for murder was not clear error.
The district court also found that Vaught’s actions on April 22 did constitute the “substantial step” required for attempted murder. The district court relied upon this court’s unpublished per curiam opinion in a case with facts very similar to this one, United States v. White, 27 Fed. Appx. 584, 2001 WL 1631439 (6th Cir.2001). In that case, we upheld a district court’s application of USSG § 2A2.1 where police, after receiving a phone call describing an armed man at a nightclub, executed a Terry stop, found a weapon on his person, and arrested him. Id. at 585. While questioning the defendant, the police learned that he had been hit by the security guards at the bar, who thought he had been involved in a fight, and that he had gone to his car, retrieved the weapon, and had returned to the club, intending to kill the security guards in retaliation. Id. In that case, the defendant argued that his conduct did not meet the level of culpability established in two earlier Sixth Circuit cases for attempt; the White court said that those cases did not “purport to establish a minimum threshold that a defendant must satisfy before he can be sentenced under § 2A2.1(a)(l).” Id. at 586.
Vaught argues on appeal that the Tennessee standard for what constitutes a “substantial step” should apply and that Tennessee law essentially requires that the action be the final step before the completion of the murder. Vaught cites several Tennessee cases in which conduct more extreme than Vaught’s was considered an attempt; in these cases, the common element was that the defendant in question had actually fired the weapon. See, e.g., State v. Lewis, 2002 WL 360269 (Tenn.Crim.App.2002) (defendant returned to a store following an argument with its owners and fired on the car in which the owners were sitting); State v. Delaney, 1999 WL 360159 (Tenn.Crim.App.1999) (defendant shot, but did not kill, an officer). That under Tennessee law these acts constituted “substantial steps” does not preclude lesser conduct’s being considered “substantial steps” as well. To take just one example, in State v. Reeves the Tennessee Supreme Court affirmed a jury verdict convicting of attempted murder where a girl placed a purse with rat poison on her teacher’s desk with intent to poison the teacher’s tea. 916 S.W.2d 909. The Tennessee Supreme Court said:
[WJhen an actor possesses materials to be used in commission of a crime, at or near the scene of the crime, and where the possession of those materials can serve no lawful purposes of the actor under the circumstances, the jury is entitled, but not required, to find that the actor has taken a “substantial step” toward the commission of the crime if such action is strongly corroborative of the actor’s overall criminal purpose.
Id. at 914. Even under the Tennessee standard, Vaught’s actions constitute a “substantial step” and are thus sufficient, along with his mens rea, to establish his liability for attempted first-degree murder for purposes of § 2A2.1(a)(l).1
[235]*235C. Upward Departure pursuant to USSG § 3C1.1 (Obstruction of Justice)
Vaught argues that the district court’s aggregation of the two instances of obstruction of justice (i.e., applying a two-level increase for each instance of obstruction) was unauthorized under the Guidelines. We noted (in dicta) in Fields v. United States the absence of any authority to support the aggregation of obstruction points when a defendant commits multiple acts of obstruction. 963 F.2d 105 (6th Cir.1992). However, in subsequent cases other circuits have held that such an aggregation is allowed under the Guidelines. See, e.g., United States v. Ventura, 146 F.3d 91, 96-97 (2nd Cir.1998); United States v. Clements, 73 F.3d 1330, 1341-42 .(5th Cir.1996).
The Fifth Circuit’s rationale in Clements, supra, is apt. The court in Clements, relying on 18 U.S.C. § 3553(b) and USSG § 5K2.0, held that a departure is appropriate when the sentencing court finds “an aggravating or mitigating circumstance of a kind, or to a degree, not adequately taken into consideration by the guidelines.” Id. at 1341. The Fifth Circuit also applied the reasonableness standard from Williams v. United States to uphold the district court’s four-level departure where the court found that the defendant had committed multiple acts of obstruction but it imposed upward departures for only two of them. Id. at 1342-43 (citing Williams v. United States, 503 U.S. 193, 203, 112 S.Ct. 1112, 117 L.Ed.2d 341 (1992)).
The Second Circuit relied on the decision in Clements when it decided United States v. Ventura, supra. The Second Circuit noted that:
[mjultiple acts of obstruction, especially when they differ in kind or have different obstructive objectives, can be found to fall sufficiently far outside the heartland conduct 3C1.1 was designed to address that departures will be warranted ... Departure may be especially justified where, as here, the defendant obstructed justice more than once through wholly discrete and unrelated acts ... Instances that are atypical in that they vary by reason of degree or seriousness, or frequency of occurrence, from the norm may justify an upward or downward departure from the normal two-level adjustment.
146 F.3d 91 at 97 (internal quotations and citations omitted). The evidence, including live testimony from one of Vaught’s fellow inmates, indicates that the intimidation of Kevin Garnett and John Hollis, Jr. were both explicit, credible threats of serious bodily harm; as such, they fall far enough “outside the heartland conduct” that the district court’s four-level departure was reasonable.
D. Upward Departure pursuant to USSG § 4A1.3 (likelihood of recidivism)
The district court also departed upward pursuant to USSG § 4A1.3, which allows an upward departure when “reliable information indicates that the criminal history category does not adequately reflect the seriousness of the defendant’s past criminal conduct or the likelihood that the defendant will commit other crimes.” Such information may include prior sentences not used in computing the criminal history category and prior similar adult criminal conduct not resulting in a criminal conviction, where applicable. On appeal, Vaught argues that the district court failed to establish the factual basis for its upward [236]*236departure under § 4A1.3, as it is required to do by 18 U.S.C. § 3353(c)(2). In United States v. Rodriguez, we interpreted § 3353(c)(2) to mean that “a short clear written statement or a reasoned statement from the bench must support [a] departure. The court is not required to incant the specific language used in the guidelines, but should identify clearly the aggravating factors and its reasons for connecting them to the permissible grounds for departure.” 893 F.2d 825, 828 (6th Cir.1990). We apply a three-prong test to evaluate a district court’s exercise of discretion under § 4A1.3:
First, we review de novo the circumstances surrounding the departure to determine whether they are sufficiently unusual to warrant divergence from the guidelines. Second, we evaluate whether the circumstances upon which the district court based the departure actually exist in the case. In reviewing the trial court’s factfinding, we reverse only for clear error. Third, once we have assured ourselves that the circumstances are proper for departure and that those circumstances enjoy support in the record, we assess the degree or range of departure for reasonableness.
United States v. Thomas, 24 F.3d 829, 832 (6th Cir.1994). In the course of the sentencing hearings, the district court both reviewed documents and heard live witness testimony that Vaught had a long history of violence and had expressed his intent to carry out his threats to harm his sister, among others, upon his release. This evidence established the unusual circumstances necessary to warrant divergence from the guidelines both on the grounds that Vaught’s criminal history category did not accurately represent his actual criminal history and that his likelihood of recidivism was relatively high.
During the April, 2002 sentencing hearing, the district court gave the parties notice that it was considering an upward departure pursuant to § 4A1.3. When it did so, the court cited (i) Vaught’s criminal history; (ii) the evidence of Vaught’s abuse of several prior girlfriends and other violent conduct which had not led to criminal convictions; (in) the evidence of repeated incidences of abusive and violent behavior toward his sister; (iv) the violent nature of much of Vaught’s criminal history, including the two bank robberies which had not been factored into his criminal history category because of their age; (v) Vaught’s ongoing substance abuse problems; and (vi) his consistent assertions that he would harm his sister, nephew, and others after his release. Although the district court did not repeat this list at Vaught’s final sentencing hearing, there is no reason to-believe that the court’s reasoning changed between the April, 2002 hearing and the final hearing, and the reasoning articulated in April of 2002 supports the district court’s two-level upward departure. We find, given the circumstances in the record, that the district court’s departure was reasonable.
E. Imposition of Five-Year Term of Supervised Release
At the final sentencing hearing, the district court imposed a five-year term of supervised release, which Vaught argues exceeded the court’s authority under the Sentencing Guidelines. Vaught pled guilty to a violation of 18 U.S.C. § 922(g)(1), which prohibits convicted felons from possessing firearms. This violation is considered a Class C felony pursuant to 18 U.S.C. § 3559(a)(3) because 18 U.S.C. § 924(a)(2) limits the punishment therefor to a term of imprisonment of “not more than ten years.” Generally, those convicted of Class C felonies are subject to a two-to three-year term of supervised release [237]*237following incarceration. 18 U.S.C. § 3583(b)(2); USSG § 5D1.2(a)(2). Under § 5D1.2 of the Sentencing Guidelines, a defendant may be sentenced to more than five years of supervised release if the Class C felony of which he was convicted is listed in 18 U.S.C. § 2332b(g)(5)(B); the felon-in-possession statute is not so listed. The United States has not cited, and the court cannot find, any support for an increase in the term of supervised release in spite of the several justified upward departures in the term of imprisonment itself.
F. Imposition of Special Condition of Supervised Release
When the district court imposed Vaught’s term of supervised release, it also imposed as a special condition of that supervised release that Vaught be confined to a mental health facility. Under § 5D1.3(b) of the Sentencing Guidelines, a court may impose a special condition of supervised release if the condition:
(1) [is] reasonably related to (A) the nature and circumstances of the offense and the history and characteristics of the defendant; (B) the need for the sentence imposed to afford adequate deterrence to the criminal conduct; (C) the need to protect the public from further crimes of the defendant; and (D) the need to provide the defendant with needed vocational training, medical care, or other correctional treatment in the most effective manner; (2) involve[s] no greater deprivation of liberty than is reasonably necessary for the purposes set forth above; and (3)[is] consistent with any pertinent policy statements issued by the Sentencing Commission.
We review a district court’s imposition of a special condition of supervised release for abuse of discretion. United, States v. Modena, 302 F.3d 626, 636 (6th Cir.2002). In order for us to undertake such a review, the district court must explain the reasoning behind its imposition. Here, the district court provided no such reasoning; we are left to speculate as to whether the court imposed the special condition due to the evidence of substance abuse, violent and abusive tendencies, or some other reason entirely.
Where the district court’s reasoning is obvious, we have upheld an imposition of special conditions. See, e.g., United States v. Berridge, 74 F.3d 113, 118 (6th Cir.1996) (district court’s failure to explain the reasons for prohibiting a defendant, who was convicted of filing false loan applications, from working in a bank was harmless error). The reasoning here, though, is not obvious. The issue of custodial mental health care was never discussed in the sentencing hearings, and the district court did not order that Vaught undergo mental health treatment while incarcerated. Furthermore, the district court did not find specific facts about any particular mental disease from which it believed Vaught suffered. It also did not address the propriety or impropriety of including in the special condition the opportunity for discharge upon proper recommendation from the mental health facility after a year of confinement. We therefore hold that, although a special condition upon Vaught’s supervised release may in fact be appropriate, the district court may not make such an imposition in this case without making specific findings of fact to support it.
G. Violation of Vaught’s Right to AIlocute
Due to the length of the sentencing hearings, Vaught waived his right to be present until the court was ready to impose its sentence. Vaught argues on appeal, and an examination of the transcript from the sentencing hearing reveals, that [238]*238he was present for the imposition of the sentence but that at no time was he afforded the opportunity for allocution, a right guaranteed to him by then-existing Fed.R.Crim.P. 32. Vaught’s counsel did not object to this failure to address the defendant at the sentencing.
Rule 32 (i) (4) (A) (ii) provides that the district court must, prior to sentencing, address the defendant personally in order to permit the defendant to speak. We held in United States v. Riascos-Suarez that a district court’s failure to do so may constitute reversible error. 73 F.3d 616, 627 (6th Cir.1996). In United States v. Carter, we reviewed a claim of failure to allow allocution for plain error where the defense failed to object at the time of the failure. 355 F.3d 920, 926 (6th Cir.2004) In that case, however, we applied the plain error review standard because the defendant alleged a limitation on his right of allocution, not a complete denial. Id. at 926, n. 3. In United States v. Wolfe, we adopted a de novo standard of review for allegations of denial of the right to allocute. 71 F.3d 611, 614 (6th Cir.1995). The court in Wolfe applied this standard because “a defendant would probably not raise an allocution issue at sentencing before the district court, because if he did the district court is likely simply to offer the defendant and his counsel the opportunity to allocute or re-allocute.” Id. at 614. In this case, then, the de novo standard of review is appropriate.
In United States v. Thomas, we specifically addressed the district court’s responsibility for affording the defendant the right to allocute:
[T]o avoid litigation arising out of ambiguous records in order to determine whether the trial judge did address himself to the defendant personally, we think that the problem should be taken out of the realm of controversy. This is easily accomplished. Trial judges before sentencing should, as a matter of good judicial administration, unambiguously address themselves to the defendant. Hereafter trial judges should leave no room for doubt that the defendant has been issued a personal invitation to speak before sentencing.
875 F.2d 559, 561 (6th Cir.1989). In this case, there is no ambiguity about whether the district judge addressed himself to the defendant directly, in accord with the mandate of Thomas; the record clearly indicates that he did not. The United States argues that Vaught’s waiver of his right to be present during some parts of the sentencing hearings also constitutes a waiver of his right to allocute; the record indicates that no such waiver was discussed or contemplated. Vaught was brought into the courtroom for key parts of the sentencing hearings, and nowhere in the discussion of his decision not to be present at certain times was there any mention of the right to allocute. While we can understand the court’s frustration with the defendant and some confusion about what portions of the sentencing hearing he wished to be present for, there is no evidence to indicate Vaught knowingly and voluntarily waived his right to allocute, and none that the district court provided the opportunity. This failure constitutes error on the part of the district court.
H. Issues Related to the United States Supreme Court’s Decision in United States v. Booker
Between the date of oral arguments in this case (December 9, 2004) and this decision, the United States Supreme Court decided United States v. Booker, — U.S. -, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005), which held unconstitutional the mandatory nature of the USSG and held: “Any fact (other than a prior conviction) [239]*239which 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.” Booker, 125 S.Ct. at 756. In this case, the district court’s upward departures for obstruction of justice and likelihood of recidivism, as well as its application of the cross-reference provision all implicate Booker. However, Vaught did not challenge these determinations on Sixth Amendment grounds during the sentencing, nor did he raise the issues in his briefs to this court or in a subsequent supplemental letter brief as Rule 28(j) of the Federal Rules of Appellate Procedure allows. Nevertheless, “this Court has discretion to correct plain errors affecting important rights of criminal defendants, even when not raised on appeal. ” United States v. Graham, 275 F.3d 490, 521 (6th Cir.2001) (considering Apprendi issue not raised before Court of Appeals) (emphasis supplied); see also Fed.R.Crim.P. 52(b).
In undertaking plain error review, we “apply ... Rule 52(b) as outlined in Olano. Under that test, before an appellate court can correct an error not raised at trial, there must be (1) ‘error,’ (2) that is ‘plain,’ and (3) that ‘affect[s] substantial rights.’ If all three conditions are met, an appellate court may then exercise its discretion to notice a forfeited error, but only if (4) the error ‘seriously affeetfs] the fairness, integrity, or public reputation of judicial proceedings.’ ” Johnson v. United States, 520 U.S. 461, 466-67, 117 S.Ct. 1544, 137 L.Ed.2d 718 (1997) (internal quotation and citation omitted).
The first prong of this test, then, requires us to determine whether, in light of Booker, a sentencing error occurred. The record indicates that the district court did err in determining Vaught’s sentence based on the presumption that the Sentencing Guidelines were mandatory. (Tr. of Sentencing, J.A. at 175.) Given the holding of Booker, this presumption was error. The second prong requires us to determine whether the error was “plain;” that is, “clear” or “obvious.” United States v. Olano, 507 U.S. 725, 734, 113 S.Ct. 1770, 123 L.Ed.2d 508 (1993). In United States v. Oliver, 397 F.3d 369, 375 (6th Cir.2005), we held that “[t]he critical question in this case is when the error must be plain ... [W]here the law at the time of trial was settled and clearly contrary to the law at the time of the appeal [ ] it is enough that an error be ‘plain’ at the time of appellate consideration.” (quoting Johnson, 520 U.S. 461 at 468, 117 S.Ct. 1544, 137 L.Ed.2d 718 (1997)) (emphasis in original). At the time of Vaught’s sentencing, it was well-settled that the Sentencing Guidelines were mandatory; Booker effected a change in the law and it is now clear that they are not, and that the district court’s reliance on them as such was error. Therefore, the first and second prongs of the plain-error test are satisfied.
The third prong of the plain-error test requires that the error have affected Vaught’s substantial rights. The United States Supreme Court held in United States v. Cotton, 535 U.S. 625, 632, 122 S.Ct. 1781, 152 L.Ed.2d 860 (2002), that this “usually means that the error ‘must have affected the outcome of the district court proceedings.’” (quoting Olano, 507 U.S. at 734, 113 S.Ct. 1770) (emphasis in original). In United States v. Barnett, 398 F.3d 516, 529 (6th Cir.2005), however, we held that “the most prudent course of action [] 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 [a defendant] would face in attempting to establish that the [240]*240sentencing court would have imposed such a sentence.”
The court in Barnett also noted the possibility that such a presumption could be rebutted by a record in which there is “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.” 398 F.3d at 529. In fact, the court in United States v. Webb, 403 F.3d 373 (6th Cir.2005), found itself confronted with just such a record, and it found that the defendant’s substantial rights were not prejudiced. There, the district court considered an upward departure based on Webb’s criminal history, referred to him as a “menace,” and sentenced him to the maximum possible sentence within the guideline range. 403 F.3d at 381-82. Here, the district court did depart upward, and expressed clear concern about Vaught’s threats of future harm, but sentenced him at the bottom of the applicable guideline range. Also, there was a significant increase in the applicable guideline range caused by the district court’s application of the cross-reference provision, USSG § 2X1.1 (10-16 months for violation of the felon-in-possession statute; even with the upward departures, this would be significantly less than the 108 months imposed under the attempted murder provision). Although we held in Section B, supra, that the district court correctly applied the cross-reference provision, this discrepancy indicates a significant possibility that the district court, within the confines of Booker’s Sixth Amendment holding, would impose a reasonable sentence lower than the one it imposed under the cross-reference provision. See United States v. Trammel, 404 F.3d 397 (6th Cir.2005) (sentence at very bottom of guideline range suggests likelihood that district court may have sentenced defendant to a lower sentence under an advisory scheme); see also United States v. Hamm, 400 F.3d 336 (6th Cir.2005) (sentence at low end of guideline range, combined with district court’s expressed sympathy for defendant, indicate likelihood that district court may have sentenced defendant to a lower sentence under an advisory scheme). Therefore, we find that Vaught satisfies the third prong of the plain-error test.
The fourth prong of the plain-error test requires us “to determine whether this case warrants the exercise of our discretion.” United States v. Rogers, 118 F.3d 466, 473 (6th Cir.1997). We will exercise that discretion in cases where the error “seriously affectfs] 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). In Barnett, we held that “... it would be fundamentally unfair to allow [a defendant’s] sentence, imposed under a mandatory Guidelines regime, to stand in light of [Booker’s] substantial development in, and alteration of, the applicable legal framework.” 398 F.3d at 530. Also, we noted the inherent unfairness of assessing the reasonableness of a sentence, as Booker mandates, where the district court “was never called upon to impose a sentence in the exercise of its discretion.” Id. (quoting United States v. Hughes, 396 F.3d 374, 381 n. 8 (4th Cir.2005)) (opinion amended on rehearing by United States v. Hughes, 401 F.3d 540 (4th Cir.2005); see similar language in amended opinion at *13, n. 14.) This case, we believe, does warrant the exercise of our discretion to correct the plain error of the district court in sentencing Vaught under the presumption of the mandatory nature of the Sentencing Guidelines.
CONCLUSION
The district court erred in imposing the five-year term of supervised release, in [241]*241failing to make findings of fact related to the special condition on the supervised release, and in failing to provide Vaught the opportunity to allocute. We therefore VACATE the sentence and REMAND to the district court for resentencing consistent with this opinion and the Supreme Court’s decision in Booker.