PER CURIAM:

This appeal arises from the district court's decision to deny Petitioner Raul Gonzalez Jr.'s 28 U.S.C. § 2255 motion collaterally attacking his sentence. We granted a Certificate of Appealability (COA) on two issues: (1) whether we should take cognizance of an issue not raised in the parties' original briefs: that the court below had abused its discretion by denying petitioner leave to amend his § 2255 motion; and (2) if we do take cognizance of this issue, whether it has merit. Having reviewed the parties' briefs and heard oral argument in this matter, we affirm.

I. FACTUAL BACKGROUND

In May of 2004, Gonzalez entered the United States Border Patrol Checkpoint near Hebronville, Texas driving a tractor trailer. A border patrol agent questioned Gonzalez about his citizenship and noticed that Gonzalez was sweating and avoiding eye contact. When asked about the contents of the trailer, Gonzalez stated that it was empty. After drug dogs alerted to the trailer, the authorities discovered 268 bundles of marijuana weighing a total of 1,476.44 kilograms. DEA agents subsequently discovered 23.58 kilograms of cocaine concealed among the bundles of marijuana.

II. PROCEDURAL HISTORY

A jury convicted Gonzalez of possession with intent to distribute marijuana and cocaine. At sentencing, counsel for Gonzalez argued that the United States Sentencing Guidelines were unconstitutional in light of the Supreme Court's decision in Blakely v. Washington, 542 U.S. 296, 124 S.Ct. 2531, 159 L.Ed.2d 403 (2004). The district court concluded that it was bound to apply the Guidelines as mandatory under United States v. Pineiro, 377 F.3d 464 (5th Cir. 2004), vacated, 543 U.S. 1101, 125 S.Ct. 1003, 160 L.Ed.2d 1006 (2005), remanded to 410 F.3d 282 (5th Cir. 2005). Gonzalez's counsel did not file a notice of appeal; therefore his conviction became final when the deadline for filing an appeal expired on February 28, 2005. See United States v. Plascencia, 537 F.3d 385, 388 (5th Cir. 2008). After Gonzalez was convicted, the Supreme Court held that the mandatory United States Sentencing Guidelines were unconstitutional. United States v. Booker, 543 U.S. 220, 263-65, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005).

In March of 2005, Gonzalez filed a pro se § 2255 motion and supporting brief in which he asserted that "[a] recent Supreme Court decision determined that the Federal Sentencing Guidelines were unconstitutional." In this motion, Gonzalez asserted that he received ineffective assistance of counsel. Gonzalez subsequently filed an additional § 2255 motion in which he argued other issues that are not relevant here. In September of 2005, at Gonzalez's request, the district court dismissed the entire proceeding without prejudice. In November of 2005, Gonzalez filed a motion requesting appointment of counsel in order to pursue a claim of ineffective assistance of counsel due to his attorney's failure to file a notice of appeal. On December 7, 2005, Gonzalez timely filed the instant § 2255 motion. In his supporting brief, he again claimed that he had received ineffective assistance of counsel, but did not mention his attorney's alleged failure to file a notice of appeal. Rather, he claimed that his attorney had committed several errors during the sentencing phase and had advised him to proceed to trial in the face of overwhelming evidence.

In July of 2006, more than one year after his conviction became final, Gonzalez filed a motion for leave to amend his § 2255 pleading to include a claim of ineffective assistance based on his attorney's failure to file an appeal. The district court refused to allow the amendment, reasoning that the failure to file an appeal "was not a newly discovered [sic] issue" that could not have been raised in the initial motion. At the time the court issued its order, the government had not yet filed its response to the petition. The district court ultimately denied the § 2255 motion and denied a COA. We granted a COA on the question of whether the district court abused its discretion when it refused to allow Gonzalez to amend his § 2255 motion. United States v. Gonzalez, No. 07-40517 (5th Cir. July 15, 2008) (unpublished COA order).

III. DISCUSSION

We first address the question of whether we should take cognizance of the issue that was not raised in the parties' original briefs: that the district court abused its discretion when it denied Gonzalez leave to amend his § 2255 motion. The government appears to have conceded this point by proceeding immediately to argument on the merits. We have previously exercised our discretion to consider unraised issues in COA petitions in light of similar concessions made by the government. See, e.g., United States v. Merrifield, 339 Fed.Appx. 374 (5th Cir. 2009) (unpublished). Of course, we are mindful of the Supreme Court's admonition that courts should "normally decide only questions presented by the parties." Greenlaw v. United States, ___ U.S. ___, 128 S.Ct. 2559, 2564, 171 L.Ed.2d 399 (2008) (internal quotation marks and citation omitted). The Supreme Court has recognized, however, that appellate courts may depart from the principle of party presentation in criminal cases to protect the rights of pro se litigants. Id. (citing Castro v. United States, 540 U.S. 375, 381-83, 124 S.Ct. 786, 157 L.Ed.2d 778 (2003)). We find that this case warrants such a departure.

In order to decide whether the district court abused its discretion by refusing to allow Gonzalez leave to amend his § 2255 motion, we must first determine whether Gonzalez filed his motion to amend within the one-year limitations period imposed by the Antiterrorism and Effective Death Penalty Act of 1996 (AEDPA). 28 U.S.C. § 2255(f)(1). We conclude that he has not. AEDPA requires a prisoner in federal custody to bring his motion for relief no later than one year after his conviction becomes final. Id. As the government emphasized in its brief and at oral argument, Gonzalez's conviction became final on February 28, 2005. Gonzalez did not seek leave to amend his § 2255 motion until July 25, 2006, well after the one-year limitations period had expired. In order to demonstrate that the district court abused its discretion, Gonzalez must overcome the time-bar on the claim raised in his proposed amendment.

Gonzalez first argues that his new claim is not time-barred because it relates back to his original § 2255 pleading under Federal Rule of Civil Procedure 15(c)(1). It is well settled that Rule 15 applies to federal habeas proceedings. See United States v. Saenz, 282 F.3d 354, 356 (5th Cir. 2002). "An amendment to a pleading relates back to the date of the original pleading when . . . the amendment asserts a claim or defense that arose out the conduct, transaction, or occurrence set out-or attempted to be set out-in the original pleading . . . ." Fed.R.Civ.P.15(c)(1)(B).

Gonzalez urges us to hold that his motion to amend automatically relates back to his original pleading because the underlying theory of the claims is the same: ineffective assistance of counsel. In addressing this question, we are guided by the Supreme Court's decision in Mayle v. Felix, in which the Court held that claims raised in an amendment to a habeas petition did not automatically relate back merely because they arose out of the same trial and conviction. 545 U.S. 644, 650, 125 S.Ct. 2562, 162 L.Ed.2d 582 (2005). The Court explained that amendments do not relate back if they assert "a new ground for relief supported by facts that differ in both time and type from those the original pleading set forth." Id. We have not yet determined how Felix's holding applies to habeas amendments seeking to add new claims of ineffective assistance of counsel to preexisting claims. Cf. United States v. Lewis, 182 Fed.Appx. 344, 345 (5th Cir. 2006) (unpublished) (declining to reach the question of whether the petitioner's amendment satisfied the relation-back test).

Two of our sister circuits, however, have held that, under Felix, one claim of ineffective assistance does not automatically relate back to another simply because the two claims both rest on a violation of the Sixth Amendment. See, e.g., United States v. Hernandez, 436 F.3d 851, 858 (8th Cir. 2006); United States v. Ciampi, 419 F.3d 20, 24 (1st Cir. 2005). In Ciampi the First Circuit applied Felix's "stringent standard" and held that a claim of ineffective assistance arising out of the attorney's alleged failure to discuss the petitioner's appellate rights with him did not relate back to the original claim dealing with the attorney's advice to accept a plea bargain. 419 F.3d at 24. The court determined that a petitioner "does not satisfy the Rule 15 `relation back' standard merely by raising some type of ineffective assistance in the original petition, and then amending the petition to assert another ineffective assistance claim based upon an entirely distinct type of attorney misfeasance." Id. (citations omitted). The Eighth Circuit echoed this reasoning, finding that claims relating to the attorney's failure to cross examine two witnesses and those relating to the failure to object to evidence were "not similar enough to satisfy the `time and type test'" espoused in Felix. Hernandez, 436 F.3d at 858.

Several pre-Felix decisions also indicate that ineffective-assistance claims should not automatically satisfy the test for relation back simply because they rest on the same constitutional violation. The Eleventh Circuit held that a petitioner's claim that his counsel failed to inform him of a possible plea agreement did not relate back to the original claim that his attorney had failed to challenge the chemical composition of the crack cocaine the petitioner was charged with possessing. Davenport v. United States, 217 F.3d 1341, 1346 (11th Cir. 2000). Prior to its decision in Hernandez, the Eighth Circuit had rejected a petitioner's claim seeking to relate claims arising out of an alleged failure to appeal back to his original claims regarding his counsel's failure to seek a downward departure at the sentencing stage. United States v. Craycraft, 167 F.3d 451, 457 (8th Cir. 1999). The Third Circuit reached a similar result in United States v. Duffus, 174 F.3d 333, 337 (3d Cir. 1999) (holding that the petitioner's amended claim of ineffective assistance due to his attorney's failure to move to suppress evidence did not relate back to his original claim that his attorney failed to raise an issue on appeal). These two decisions, along with Ciampi are particularly relevant to the instant case because Gonzalez seeks to relate a claim dealing with his appellate rights to prior claims arising from his attorney's ineffective assistance during pretrial proceedings and at the sentencing stage.

We agree with the approach adopted by our sister circuits. New claims of ineffective assistance of counsel do not automatically relate back to prior ineffective assistance claims simply because they violate the same constitutional provision. Rather, we must look to whether Gonzalez's new claim asserts "a new ground for relief supported by facts that differ in both time and type from those the original pleading set forth." Mayle v. Felix, 545 U.S. 644, 650, 125 S.Ct. 2562, 162 L.Ed.2d 582 (2005). If it does, then his proposed amendment does not relate back to his original pleading and is time-barred.

We conclude that Gonzalez's proposed amendment does raise a new ground for relief. Gonzalez's original § 2255 motion alleged that his attorney had committed errors during the sentencing phase that resulted in Gonzalez's disqualification for downward departures from his sentencing range under the Guidelines. The pleading also alleged that Gonzalez's attorney had coerced him into proceeding to trial in the face of overwhelming evidence. The proposed amendment, however, asserts a claim of ineffective assistance of counsel based on the attorney's failure to file an appeal. "Failing to file an appeal is a separate occurrence in both time and type," from conduct that occurs at the sentencing phase and before trial. Cray-craft, 167 F.3d at 457. Gonzalez's original claims involve "entirely distinct type[s] of attorney misfeasance" from the claim asserted in his proposed amendment. United States v. Ciampi 419 F.3d 20, 24 (1st Cir. 2005). Because the proposed amendment raises a new claim and therefore does not relate back to the original § 2255 motion, it is time-barred under AEDPA.

Gonzalez also argues that the district court abused its discretion by denying leave to amend his claim when leave of the court was not required. Under the former version of Rule 15(a)(1)(A), which was in effect when Gonzalez filed his motion to amend, "[a] party may amend its pleading once as a matter of course before being served with a responsive pleading." Fed.R.Civ.P. 15(a)(1)(A) (amended 2009). Here, the record indicates that, at the time Gonzalez filed his motion, the government had yet to file its response. The district court appears to have treated this motion under Rule 15(a)(2), which governs motions to amend after a responsive pleading has been filed.

We agree with Gonzalez that the district court erred on this point. Our precedent indicates, however, that a district court may deny motions to amend, even when such amendment would be "as a matter of course," when the amendment would be futile. Johnson v. Dunbar, No. 92-09536, 1994 WL 35605 at *4 (5th Cir. Jan. 27, 1994), see also Avatar Exploration, Inc. v. Chevron, U.S.A., Inc., 933 F.2d 314, 321 (5th Cir. 1991) (citations omitted). Although the district court did not address futility in its order, we may affirm for any reason supported by the record, even if not relied on by the district court. LLEH, Inc., v. Wichita County, Tex., 289 F.3d 358, 364 (5th Cir. 2002) (citations omitted). Having determined that Gonzalez's amendment does not relate back to his original claims and is therefore time-barred, we conclude that his amendment would have been futile, thus rendering the district court's procedural error inconsequential.

For the foregoing reasons, the decision of the district court is hereby AFFIRMED.