Full Life Hospice is a hospice care provider participating in the federal Medicare program. Over a number of years, it provided hospice care services to terminally ill Medicare beneficiaries and sought reim *1014 bursement for these services from the Department of Health and Human Services (HHS). A fiscal intermediary, acting on behalf of HHS, later contested some of these reimbursements and demanded repayment of funds that it claimed were distributed in excess of a spending cap.

Full Life then unsuccessfully challenged HHS intermediary’s determination through an administrative appeal, which was denied as untimely. On appeal to the district court, the court found no basis to excuse Full Life’s untimely challenge. We agree with the district court that it lacked subject matter jurisdiction because of Full Life’s failure to file a timely administrative appeal. Accordingly, exercising jurisdiction under 28 U.S.C. § 1291 , we AFFIRM.

I. Background

A. Statutory and Regulatory Background

Medicare pays hospice care providers a predetermined amount for each day a Medicare beneficiary receives hospice care. See 42 U.S.C. § 1395f(i)(l)(A). This amount is subject to a spending cap. Id. § 1395f(2). HHS has adopted a regulation, 42 C.F.R. § 418.309 , to calculate the amount of this cap.

The Medicare Act allows for challenges to regulations such as 42 C.F.R. § 418.309 , but it establishes a specific procedure for bringing such claims. 1 As is relevant here, this process can begin with a hospice provider’s challenge to the basis for a request for repayment made by an HHS fiscal intermediary. HHS uses fiscal intermediaries to calculate, in accord with the relevant statutes and regulations, the spending cap for a particular hospice provider within an accounting year. See 42 U.S.C. §§ 1395h, 1395kk-l.

If the provider “is dissatisfied with a final determination” made by a fiscal intermediary and the amount in controversy exceeds $10,000, the provider can request a hearing on the matter with the Provider Reimbursement Review Board (the Board). Id. § 1395oo(a)(l)(A)(i), (a)(2). A provider is required to file a request for such a hearing with the Board “within 180 days after notice of the intermediary’s final determination.” Id. § 1395oo(a)(3). Under limited circumstances, the Board can extend the 180-day time period within which to challenge a fiscal intermediary’s final determination upon a “good cause showing by the provider.” 42 C.F.R. § 405.1836 (a). 2

*1015 The Medicare Act allows for a slightly different process for direct challenges to HHS regulations. If the provider contesting a reimbursement amount has filed a request for a hearing in accord with § 1395oo(a) (mentioned above), the provider “may file a request for a determination by the Board of its authority to decide the question of law or regulations relevant to the matters in controversy.” 42 U.S.C. § 1395oo(f)(l). The parties both refer to this type of request as expedited judicial review (EJR).

After a validly filed request for EJR, the Board “shall render such determination [of its authority to rule on a matter] in writing within thirty days after the Board receives the request and such accompanying documents and materials, and the determination shall be considered a final decision and not subject to review by the Secretary.” Id. § 1395oo(f)(l). If the Board fails to render such a decision within the thirty-day period, “the provider may bring a civil action [in United States District Court] (within sixty days of the end of such period) with respect to the matter in controversy contained in such request for a hearing.” Id.

Finally, outside of the context of EJR, the Medicare Act requires that “[providers shall have the right to obtain judicial review of any final decision of the Board, or of any reversal, affirmance, or modification by the Secretary, by a civil action commenced within 60 days of the date on which notice of any final decision by the Board or of any reversal, affirmance, or modification by the Secretary is received.” 42 U.S.C. § 1395oo(f)(l). The statute further mandates that “[a] decision of the Board shall be final unless the Secretary, on [her] own motion, and within 60 days after the provider of services is notified of the Board’s decision, reverses, affirms, or modifies the Board’s decision.” Id.

With the statutory and regulatory framework in mind, we turn to Full Life’s challenge to HHS’s decision.

B. Procedural Background

A fiscal intermediary, acting on behalf of HHS, issued three notices challenging the amount of Full Life’s reimbursements for hospice services on September 25, 2008, May 27, 2009, and March 10, 2010. In these notices, the fiscal intermediary informed Full Life that it had received reimbursements for hospice care in excess of the amount permitted by 42 C.F.R. § 418.309 . Full Life started to repay the excess amount at some point shortly after receiving these notices.

Then, on November 24, 2010, Full Life filed an administrative challenge to the notices. All three of the challenges came more than 180 days after Full Life had received the notices from the fiscal intermediary. As explained in its complaint, Full Life filed the appeals only after learning that other hospice providers had successfully challenged the validity of § 418.309.

On January 7, 2011, although the Board had not rendered any decision on Full Life’s appeals, Full Life filed suit in federal court raising a claim that § 418.309 was contrary to its authorizing statute. Several days later, on January 14, 2011, the Board issued three decisions on Full Life’s appeals, finding that each appeal was not timely filed and that Full Life had not shown “good cause” to excuse the late filing. The Board therefore concluded that it did not have jurisdiction over Full Life’s appeals.

Meanwhile, in the district court, Full Life sought to amend its complaint. In the original complaint, Full Life invoked 42 U.S.C. § 1395oo(f)(l) as one basis for subject matter jurisdiction. In its pro *1016 posed amended complaint, Full Life alleged that the district court also had subject matter jurisdiction under a number of other statutes, including (as is relevant here) the federal mandamus statute, 28 U.S.C. § 1361 .

HHS then moved to dismiss Full Life’s amended complaint. The district court granted HHS’s motion to dismiss, reasoning that because Full Life did not adhere to the statutory scheme outlined in 42 U.S.C. § 1395oo(f)(l), it could not rely on the Medicare Act as a basis for subject matter jurisdiction. The district court also determined that none of the other bases for subject matter jurisdiction noted in the amended complaint in fact applied.

Full Life then moved for leave to amend its complaint to include attacks on the Board’s three findings that Full Life had not demonstrated good cause in filing late appeals. The district court denied this motion on the ground that it was futile.

II. Analysis

Full Life challenges both the district court’s grant of the motion to dismiss and its denial of the motion to amend. Full Life argues the court erred in failing to find jurisdiction either under § 1395oo(f)(l) of the Medicare Act or under the federal mandamus statute, 28 U.S.C. § 1361 . Full Life also challenges the district court’s denial of the motion to amend the complaint to expand its challenges to HHS’s good cause determinations.

We address each of these claims in turn.

A. Subject Matter Jurisdiction

Full Life first challenges the district court’s finding that it lacked subject matter jurisdiction under 42 U.S.C. § 1395oo(f)(l). “Our review of the district court's dismissal for lack of subject matter jurisdiction is de novo.” Marcus v. Kansas Dep’t of Revenue, 170 F.3d 1305, 1309 (10th Cir.1999) (citation omitted). Further, “[b]ecause the jurisdiction of federal courts is limited, there is a presumption against our jurisdiction, and the party invoking federal jurisdiction bears the burden of proof.... A court lacking jurisdiction cannot render judgment but must dismiss the cause at any stage of the proceedings in which it becomes apparent that jurisdiction is lacking.” Id.

As we described above, § 1395oo(f)(l) limits the means by which we review challenges to the determinations made by HHS fiscal intermediaries. Most importantly, the statute requires that a provider must first obtain a hearing with the Board. To obtain such a hearing, the provider must satisfy three prerequisites: (1) the provider must be “dissatisfied” with a decision of a fiscal intermediary; (2) the amount in controversy must exceed $10,000; and (3) the provider must request a hearing “within 180 days after notice of the intermediary’s final determination.” 42 U.S.C. § 1395oo(a).

Only after these preconditions are met does § 1395oo(f)(l) require the Board to render “[a] determination in writing within thirty days after the Board receives the [EJR] request.” Finally, if the Board fails to meet its statutory obligations, “the provider may bring a civil action (within sixty days of the end of such period) with respect to the matter in controversy contained in such request for a hearing.” Id.

Full Life concedes that it did not file its requests for a hearing within the 180-day period mandated by the statute. Thus, Full Life cannot meet one of the statutory preconditions for obtaining judicial review, and the district court rightly determined that § 1395oo(f)(l) could not *1017 serve as the basis for subject matter jurisdiction.

Our conclusion here is bolstered by the Supreme Court’s recent decision addressing § 1395oo(a). In Sebelius v. Auburn Regional Medical Center, — U.S. -, 133 S.Ct. 817 , 184 L.Ed.2d 627 (2013), a number of hospitals alleged that they had been under-compensated by a fiscal intermediary because of the flawed calculations relied upon by the intermediary in calculating the amount of a particular Medicare reimbursement. The hospitals were only prompted to act after they learned the Board had determined that the intermediary had used the same flawed methodology in calculating the reimbursement for a different hospital. Similar to Full Life, the hospitals in Auburn acted many years after the 180-day deadline for appeal to the Board outlined in § 1395oo(a)(3). The Board therefore dismissed the hospitals’ appeal as untimely and the federal district court dismissed the hospitals’ subsequent complaint on the same ground. The Supreme Court ultimately affirmed the judgment of the district court, determining that § 1395oo(a)(3) was nonjurisdictional in nature, that HHS could extend the 180-day deadline for good cause, and that principles of equitable tolling did not apply to § 1395oo.

Auburn only reinforces our conclusion that the district court correctly dismissed Full Life’s complaint. Just like the hospitals in Auburn, Full Life realized that it might have a basis to challenge the calculation of a fiscal intermediary. Yet Full Life made this realization after the time allowed for such challenges had passed. Thus, like the hospitals in Auburn, Full Life’s challenge is similarly time-barred.

Full Life resists this straightforward conclusion by suggesting that it would contradict the reasoning of Bethesda Hospital Ass’n v. Bowen, 485 U.S. 399 , 108 S.Ct. 1255 , 99 L.Ed.2d 460 (1988); Minnesota Hospital Ass’n v. Bowen, 703 F.Supp. 780 (D.Minn.1988); and Affinity Healthcare Services, Inc. v. Sebelius, 746 F.Supp.2d 106 (D.D.C.2010). Full Life also relies on portions of the legislative history of § 1395oo, as supportive of a different reading of § 1395oo.

None of these authorities persuades us to reach a different result. In the cases Full Life cites, the provider had either timely appealed a decision of a fiscal intermediary or the timing of the appeal was not in dispute. Similarly, the legislative history Full Life references is silent on the scenario presented here: where a provider has failed to timely appeal to the Board. 3

Finally, Full Life’s reliance on the mandamus statute, 28 U.S.C. § 1361 , as an alternative basis for jurisdiction also fails. “Mandamus relief is available to a plaintiff only if he has exhausted all other avenues of relief and only if the defendant owes him a clear nondiscretionary duty.” Bartlett Mem’l Med. Ctr., Inc. v. Thompson, 347 F.3d 828 , 835 (10th Cir.2003) (internal quotations and citation omitted). Full Life cannot show exhaustion because it could have pursued alternative means— namely, in the statutory scheme created by § 1395oo(f)(l) — to obtain the relief it sought. See also Your Home Visiting *1018 Nurse Seros., Inc. v. Sec’y of HHS, 132 F.3d 1135, 1141 (6th Cir.1997), aff'd sub nom., Your Home Visiting Nurse Servs., Inc. v. Shalala, 525 U.S. 449 , 119 S.Ct. 930 , 142 L.Ed.2d 919 (1999) (noting that a provider’s failure to appeal a decision of a fiscal intermediary to the Board “would preclude mandamus review of that determination”). The mandamus statute therefore does not provide an alternative basis for jurisdiction.

In sum, the district court did not err in dismissing Full Life’s complaint.

B. Denial of Motion to Amend

Full Life also challenges the district court’s denial of the motion to amend the complaint. The proposed amended complaint would have added a claim challenging the Board’s determinations that Full Life had not demonstrated good cause to excuse its untimely requests for EJR. The district court denied this motion as futile in part because it determined that Full Life’s new claim would be time-barred and did not relate back under Rule 15(c) of the Federal Rules of Civil Procedure.

While Rule 15 provides that leave to amend a complaint shall be freely given when justice so requires, a district court may refuse to allow amendment if it would be futile. See Anderson v. Suiters, 499 F.3d 1228, 1238 (10th Cir.2007). “A proposed amendment is futile if the complaint, as amended, would be subject to dismissal.” Bradley v. Val-Mejias, 379 F.3d 892, 901 (10th Cir.2004). As is the case here, where leave was denied “based on a determination that amendment would be futile, our review for abuse of discretion includes de novo review of the legal basis for the finding of futility.” Cohen v. Longshore, 621 F.3d 1311, 1314 (10th Cir.2010).

Under the Medicare statute, a provider may seek judicial review of any final decision of the Board within sixty days of that decision being made. Here, the Board made its decision that Full Life lacked good cause for a late appeal on January 14, 2011. On May 11, 2011, over sixty days after the ruling from the Board (and after the district court had dismissed its complaint for want of subject matter jurisdiction), Full Life moved to amend its complaint and add challenges to the Board’s good cause determinations.

Full Life’s claim would normally be time-barred by this statute of limitations unless it related back to the original complaint. According to Federal Rule of Civil Procedure 15(c)(1)(B), an amendment “relates back” to the date of the original pleading if the “amendment asserts a claim ... that arose out of the conduct, transaction, or occurrence set out — or attempted to be set out — in the original pleading.” At the same time, an amendment does not relate back “when it asserts a new ground for relief supported by facts that differ in both time and type ft-om those the original pleading set forth.” Mayle v. Felix, 545 U.S. 644, 650 , 125 S.Ct. 2562 , 162 L.Ed.2d 582 (2005). A new pleading cannot relate back if the effect of the new pleading “is to fault [the defendants] for conduct different from that identified in the original complaint,” even if the new pleading “shares some elements and some facts in common with the original claim.” United States ex rel. Miller v. Bill Harbert Int’l Constr., Inc., 608 F.3d 871 , 881 (D.C.Cir.2010) (internal citation and quotation marks omitted), ce rt. denied, — U.S. -, 131 S.Ct. 2443 , 179 L.Ed.2d 1208 (2011); see also Hernandez v. Valley View Hasp. Ass’n, 684 F.3d 950, 961 (10th Cir.2012); 6A Wright & Miller, Federal Practice and Procedure, § 1497 (3d ed. 2012).

Full Life argues its amendment fits into the definition of relation back outlined in Rule 15 and that the district court therefore erred in denying Full Life’s motion to amend. We disagree. Full Life’s original complaint raised claims attacking the va *1019 lidity of 42 C.F.R. § 418.309 . The allegations in this complaint were premised on the fact that Full Life did not need to wait for any ruling from the Board to bring suit in federal court.

In contrast, Full Life’s proposed amended claim was supported by facts that differ in both “time and type” from the original pleadings. The new claim attacked a procedural ruling of the Board, not a rulemaking from HHS. And the new claim was premised on a fact not available at the time of the filing of the original complaint: namely, the adverse ruling on good cause, which was issued by the Board after Full Life filed its original complaint. Thus, while the proposed amended claim “shares some elements and facts in common with the original claim,” the effect of the amended claim is to fault HHS for conduct unrelated to allegations raised in the original complaint. 4

Accordingly, granting the amendment would have been futile because the amended complaint would have been subject to dismissal as time-barred under the 180-day rule of 42 U.S.C. § 1395oo(f)(l).

III. Conclusion

Based on the foregoing analysis, we AFFIRM the judgment of the district court.

. In fact, a number of Medicare providers have successfully challenged the validity of 42 C.F.R. § 418.309 , arguing that it contradicts the language of the authorizing statute. See, e.g., Los Angeles Haven Hospice, Inc. v. Sebelius, 638 F.3d 644 (9th Cir.2011); Lion Health Servs., Inc. v. Sebelius, 635 F.3d 693 (5th Cir.2011). HHS continues to defend the validity of this regulation, though HHS has withdrawn an appeal before this court of a district court ruling that invalidated this regulation. See Hospice of New Mexico, LLC v. Sebelius, 435 Fed.Appx. 749 (10th Cir.2011). And HHS has issued a new rule on the spending cap in light of these legal challenges. See Medicare Program; Hospice Wage Index for Fiscal Year 2012, 76 Fed.Reg. 47,302, 47,308-10 (Aug. 4, 2011) (to be codified at 42 C.F.R. pt. 418).

. The Board may find good cause "only if the provider demonstrates in writing it could not reasonably be expected to file timely due to extraordinary circumstances beyond its control (such as a natural or other catastrophe, fire, or strike)____" 42 C.F.R. § 405.1836 (b). This same regulation mandates that the Board "may not grant a request for an extension under this section if ... the provider relies on a change in the law, regulations, [Centers for Medicare and Medicaid Services] Rulings, or general CMS instructions (whether based on a court decision or otherwise) or a CMS administrative ruling or policy as the basis for the extension request.” Id. § 405.1836(c)(1).

. Full Life also cites to an unpublished district court order in which the "court decline!)!] to implicitly endorse an administrative ruling which intends to continue using [ 42 C.F.R. § 418.309 ,] which courts have found invalid.” Hospice Ctr. of Se. Okla., Inc. v. Sebelius, CIV-10-401-RAW, 2011 WL 2745914 , at *1 (E.D.Okla. July 12, 2011). Again, regardless of the validity of 42 C.F.R. § 418.309 , which is an issue we need not address here, the statutory scheme outlined in § 1395oo(f)(l) is clearly valid and precludes review of Full Life's attack on the fiscal intermediary’s calculation of the reimbursement cap.

. The government suggests that 42 C.F.R. § 405.1836 (e)(4) provides another basis for finding that a motion to amend would be futile. This regulation states: "A finding by the Board or the Administrator that the provider did or did not demonstrate good cause for extending, the time for requesting a Board hearing is not subject to judicial review.” Although the district court reasoned that 42 C.F.R. § 405.1836 (e)(4) precluded judicial review of the Board's good cause determinations, the government has provided no explanation as to the statutory basis for this jurisdiction-stripping regulation. Moreover, we have previously found similar regulations to be invalid because the limitations they impose on judicial review were not delegated to the agency by Congress. See, e.g., Nagahi v. I.N.S., 219 F.3d 1166 (10th Cir.2000). In this case, however, we need not rule on the validity of 42 C.F.R. § 405.1836 (e)(4), as the district court correctly determined that the proposed amendment did not relate back to the original complaint for purposes of Rule 15.