Chad Eric Simpson pled guilty to conspiracy to possess with intent to distribute and distribute cocaine, methamphetamine, and Ecstasy, 21 U.S.C. § 846 (2000) (Count One); aiding and abetting kidnapping, 18 U.S.C. §§ 1201, 2 (2000) (Count Five); and brandishing a firearm during a crime of violence, aiding and abetting, 18 U.S.C. §§ 924(c), 2 (2000) (Count Six). He was sentenced to a term of 294 months imprisonment. Simpson appeals his sentence, contending for the first time that the district court erred under Blakely v. Washington, 542 U.S. 296, 124 S.Ct. 2531, 159 L.Ed.2d 403 (2004), when it applied the cross reference from kidnapping to attempted murder, U.S. Sentencing Guidelines Manual §§ 2A4.1(b)(7), 2A2.1 (2003), although he did not admit participating in *522attempted murder. Simpson also contests the enhancements made under § 2A2.1 for kidnapping and permanent or life-threatening bodily injury and under § 3A1.3 for physical restraint. He further claims that the court erred by failing to depart downward based on his claim of coercion and duress and other grounds. Last, he challenges the court’s calculation of his criminal history. For the reasons explained below, we affirm the court’s determination of Simpson’s criminal history, but we vacate the sentence and remand for resentencing.
In United States v. Booker,—U.S.-, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005), the Supreme Court held that the federal sentencing guidelines, under which courts were required to impose sentencing enhancements based on facts found by the court by a preponderance of the evidence, violated the Sixth Amendment because of their mandatory nature. Id. at 746, 750 (Stevens, J., opinion of the Court). The Court remedied the constitutional violation by making the guidelines advisory through the removal of two statutory provisions that had rendered them mandatory. Id. at 746 (Stevens, J., opinion of the Court); id. at 756-57 (Breyer, J., opinion of the Court). Although Simpson did not raise a Sixth Amendment challenge at sentencing, this court has held that a mandatory enhancement based on judicial factfinding supported by a preponderance of the evidence constitutes plain error warranting correction when the sentence “exceeded the maximum allowed based on the facts found by the jury alone” and the record does not disclose what discretionary sentence the district court would have imposed under an advisory guideline scheme. United States v. Hughes, 401 F.3d 540, 547-48 (4th Cir.2005) (citing United States v. Olano, 507 U.S. 725, 731-32, 113 S.Ct. 1770, 123 L.Ed.2d 508 (1993)).
In light of Booker and Hughes, we find that the district court plainly erred in sentencing Simpson and that the error was prejudicial. We thus exercise our discretion to notice the error and remand for resentencing.
Simpson claims that the court erred in refusing to depart downward. However, the district court’s discretionary decision not to depart below the guideline range is not reviewable unless the court’s decision was based on a mistaken belief that it lacked authority to depart. United States v. Wood, 378 F.3d 342, 351 n. 8 (4th Cir.2004). Our review of the district court’s ruling on Simpson’s departure motion leaves us convinced that the district court understood its authority to depart and exercised its discretion not to depart.
We find no merit in Simpson’s contention that the district court erred in awarding one criminal history point for each of the Kentucky sentences listed in ¶¶ 38 and 39 of the presentence report (a fine and two days imprisonment) and for the North Carolina probationary sentence listed in ¶40 because he was not represented by counsel in any of these proceedings. He claims that the district court did not address his contention that he was denied counsel because the state court judge did not intend to impose a sentence of imprisonment (¶38) or any additional jail time (¶¶ 39, 40).
We note first that the presentence report contained information that Simpson waived counsel in the North Carolina proceeding described in ¶ 40. Although Simpson asserted in the district court that any waiver was not knowing and voluntary, he offered no evidence in support of his claim. With respect to the other sentences, Simpson’s Kentucky driving-while-impaired offenses were both misdemeanors, punishable as first and second offenses by a maximum of thirty days and six *523months imprisonment, respectively. Ky. Rev.Stat. Ann. § 189A.010 (Baldwin 2004).1 The background commentary to USSG § 4A1.2 states that all “[p]rior sentences, not otherwise excluded, are to be counted in the criminal history score, including uncounseled misdemeanor sentences where imprisonment was not imposed.” However, in Nichols v. United States, 511 U.S. 738, 748-49, 114 S.Ct. 1921, 128 L.Ed.2d 745 (1994), the Supreme Court held that a prior uncounseled misdemeanor conviction may be used to enhance the sentence for a subsequent offense only if no prison term was imposed. Simpson did not receive any prison sentence for the conviction described in H 38, but he served two days in prison for the conviction in 1139.
A defendant may challenge at sentencing the validity of a prior conviction on the ground that he was denied counsel, Custis v. United States, 511 U.S. 485, 495, 114 S.Ct. 1732, 128 L.Ed.2d 517 (1994). However, he bears the burden of showing that the prior conviction is invalid. United States v. Jones, 977 F.2d 105, 110 (4th Cir.1992). Simpson had to overcome the presumption that the state court informed him of his right to counsel as it was required by statute to do and that, if he was not represented, it was because he waived his right to counsel. Parke v. Raley, 506 U.S. 20, 28-34, 113 S.Ct. 517, 121 L.Ed.2d 391 (1992) (holding that presumption of regularity that attaches to final judgments makes it appropriate for defendant to have burden of showing irregularity of prior plea). He did not meet this burden because he did not present either evidence or testimony to establish that he had not waived counsel. We conclude that the court did not err in finding that Simpson had not been denied his right to counsel.
In conclusion, we affirm the district court’s determination of Simpson’s criminal history score, but we vacate his sentence and remand for proceedings consistent with Hughes2 Id. at 546 (citing Booker, 125 S.Ct. at 764-65, 767 (Breyer, J., opinion of the Court)). Just as we noted in Hughes, “[we of course offer no criticism of the district court judge, who followed the law and procedure in effect at the time]” of Simpson’s sentencing. Hughes, 401 F.3d at 545 n. 4. See generally Johnson v. United States, 520 U.S. 461, 468, 117 S.Ct. 1544, 137 L.Ed.2d 718 (1997) (stating that an error is “plain” if “the law at the time of trial was settled and clearly contrary to the law at the time of appeal”). We dispense with oral argument because the facts and legal contentions are adequately presented in the materials before the court and argument would not aid the decisional process.
*524 AFFIRMED IN PART, VACATED IN PART, AND REMANDED
. For guideline purposes, a "felony offense" means any offense punishable by a term of imprisonment exceeding one year, even an offense classified as a misdemeanor under state law, United States v. Raynor, 939 F.2d 191, 194-95 (4th Cir.1991), and even though, after the defendant's conviction, the maximum sentence may have been reduced to less than a year. United States v. Johnson, 114 F.3d 435, 445 (4th Cir.1997).
. Although the sentencing guidelines are no longer mandatory, Booker makes clear that a sentencing court must still "consult [the] Guidelines and take them into account when sentencing." 125 S.Ct. at 767. On remand, the district court should first determine the appropriate sentencing range under the guidelines, making all factual findings appropriate for that determination. Hughes, 401 F.3d at 546. The court should consider this sentencing range along with the other factors described in 18 U.S.C.A, § 3553(a) (West 2000 & Supp.2005), and then impose a sentence. Id. If that sentence falls outside the guidelines range, the court should explain its reasons for the departure as required by 18 U.S.C.A. § 3553(c)(2). Id. The sentence must be "within the statutorily prescribed range and ... reasonable.” Id. at 547.