Plaintiffs, the Western Shoshone Business Council (Council), suing for and on behalf of the Western Shoshone Tribe of the Duck Valley Reservation (Western Shoshones), and the law firm Edwards, McCoy & Kennedy (EM & K), appeal the decision of the district court granting defendant Secretary of the Interior’s motion to dismiss and denying plaintiffs’ motions for leave to file an amended complaint.
In 1989, the Council approved a contract with EM & K for legal services and submitted it to the Acting Area Director of the Bureau of Indian Affairs (BIA) for approval, pursuant to 25 U.S.C. § 81.1 The Acting Area Director determined that because the Western Shoshones did not appear on a list of. federally recognized tribes,2 see 53 Fed. Reg. 52,829-02 (1988), the contract was between private parties and did not inquire BIA approval. This decision was later affirmed by the Interior Board of Indian Appeals (IBIA). Edwards, McCoy & Kennedy v. Acting Phoenix Area Director, 18 I.B.I.A. 454 (1990).
Plaintiffs then brought this action in district court seeking declaratory and injunctive relief setting aside defendant’s refusal to review the contract and holding that the Western Shoshones are a federally recognized Indian tribe. The district court concluded that because they could pursue a procedure for becoming federally recognized, see 25 C.F.R. pt. 83, plaintiffs had failed to exhaust their administrative remedies and jurisdiction was therefore lacking.
The district court’s determination regarding jurisdiction is a legal one, which we review de novo. Boise City Fanners Cooperative v. Palmer, 780 F.2d 860, 866 (10th Cir.1985). We are free to affirm a district court’s decision on any grounds for which there is a record sufficient to support conclusions of law. Medina v. City & County of Denver, 960 F.2d 1493, 1495 n. 1 (10th Cir.1992).
I
Under the judicial review provisions of the Administrative Procedure Act, 5 U.S.C. §§ 701-706, “[ajgency action made reviewable by statute and final agency action for which there is no other adequate remedy in a court are subject to judicial review.” Id. § 704. The regulations regarding appeals from BIA decisions provide that a decision made by an Area Director may be appealed to the IBIA, 25 C.F.R. § 2.4(e), and that the IBIA is the final authority for the Department of the Interior on administrative actions by BIA officials. 43 C.F.R. *1055§ 4.1(b)(2)(i). Plaintiffs pursued their appeal of defendant’s refusal to review their contract to the highest authority available to them within the Department of the Interior.3 Plaintiffs were not required to pursue any other administrative avenue before seeking judicial review of defendant’s decision. For purposes of the APA, the IBIA decision was final agency action. That is only the first step, however, in our jurisdictional analysis.
II
We turn next to whether plaintiffs have standing to bring this appeal. Plaintiffs must meet both the constitutional requirements subsumed by the Article III “case or controversy” limitation on judicial power and the judicially created prudential requirements under the APA. See Association of Data Processing Serv. Orgs., Inc. v. Camp, 397 U.S. 150, 90 S.Ct. 827, 25 L.Ed.2d 184 (1970).
The Supreme Court has summarized the constitutional limitations on standing as follows:
[A]t an irreducible minimum, Art. Ill requires the party who invokes the court’s authority to show that he personally has suffered some actual or threatened injury as a result of the putatively illegal conduct of the defendant, and that the injury fairly can be traced to the challenged action and is likely to be redressed by a favorable decision.
Valley Forge Christian College v. Americans United for Separation of Church & State, Inc., 454 U.S. 464, 472, 102 S.Ct. 752, 758, 70 L.Ed.2d 700 (1982) (quotations and citations omitted).
Under § 702 of the Administrative Procedure Act, “[a] person suffering legal wrong because of agency action, or adversely affected or aggrieved by agency action within the meaning of a relevant statute, is entitled to judicial review thereof.” Thus, a plaintiff claiming a right to sue under the APA must “identify some ‘agency action’ that affects him in the specified fashion; it is judicial review ‘thereof to which he is entitled.” Lujan v. National Wildlife Fed’n, 497 U.S. 871, 882, 110 S.Ct. 3177, 3185, 111 L.Ed.2d 695 (1990). Then the prospective plaintiff must show that this agency action has caused him to suffer “legal wrong,” or that he is “adversely affected or aggrieved” by that action. Id. at 883, 110 S.Ct. at 3186. Because a determination that a plaintiff has suffered legal wrong as the result of agency action goes to the merits, courts have focused on adverse effect or aggrievement in ascertaining standing under the APA.
Adverse effect or aggrievement, in turn, has been interpreted as requiring a plaintiff to show that “the interest sought to be protected ... is arguably within the zone of interests to be protected or regulated by the statute or constitutional guarantee in question.” Data Processing, 397 U.S. at 153, 90 S.Ct. at 829; see also Lujan, 497 U.S. at 883, 110 S.Ct. at 3186; Clarke v. Securities Indus. Ass’n, 479 U.S. 388, 396, 107 S.Ct. 750, 755, 93 L.Ed.2d 757 (1987).
A
Although EM & K has an interest that is arguably threatened by defendant’s refusal to review its contract with the Council, it is clear that EM & K does not fall within the zone of interests protected or regulated under 25 U.S.C. § 81. EM & K focuses on a portion of the Supreme Court’s explanation of the zone of interests test in Clarke, that “there need be no indication of congressional purpose to benefit the would-be plaintiff,” 479 U.S. at 399-400, 107 S.Ct. at 757, and reasons that because its right to contract with the Council is regulated under § 81 it is thereby entitled to challenge defendant’s action. We are more persuaded by the unequivocal limitation on standing immediately preceding the above-quoted language: “[TJhe test denies a right of review if the plaintiffs interests are so marginally related to or inconsistent with the purposes implicit in the statute that it cannot reasonably be *1056assumed that Congress intended to permit the suit.” 479 U.S. at 399, 107 S.Ct. at 757.
It is well settled that § 81 was “intended to protect the Indians from improvident and unconscionable contracts.” In re Sanborn, 148 U.S. 222, 227, 13 S.Ct. 577, 579, 37 L.Ed. 429 (1893). Several courts have, on this basis, denied standing to challenge BIA decisions under § 81 to the non-Indian contracting party. See, e.g., Schmit v. International Finance Management Co., 980 F.2d 498 (8th Cir.1992) (per curiam); Enterprise Management Consultants, Inc. v. United States ex rel. Hodel, 685 F.Supp. 221, 223 (W.D.Okla.1988) (“plaintiff is not even arguably within the ‘zone of interest’ to be protected by [§ 81]”), aff'd on other grounds, 883 F.2d 890 (10th Cir.1989); United States ex rel. Shakopee Mdewakanton Sioux Community v. Pan American Mgmt Co., 616 F.Supp. 1200, 1208 (D.Minn.1985) (“The potential economic interest of nonlndians in a contractual relationship with a tribe is not within the intended purview of the statute.”), appeal dismissed, 789 F.2d 632 (8th Cir. 1986). We agree with the reasoning behind these decisions. Of course plaintiff EM & K is “regulated” by § 81, but the undisputed purpose of the statute is to protect tribal lands, not to regulate lawyers specifically, or to create either an administrative right of review or a contract cause of action for non-Indian contractors. Given the overtly paternalistic cast of § 81, we conclude that “it cannot reasonably be assumed that Congress intended to permit the suit,” Clarke, 479 U.S. at 399, 107 S.Ct. at 757, by non-Indian contractors.
Plaintiff EM & K does not have standing under the APA to bring this action.
B
Insofar as defendant’s refusal to review the contract between the Council and EM & K casts a cloud over their transaction and prevents the Council from obtaining the legal services it desires, the Council can show injury in fact, traceable to defendant’s action and redressable by a favorable ruling. Nevertheless, we hold that the Council is not within the zone of interests protected or regulated by § 81. By its terms, § 81 covers only those contracts “made by any person with any tribe of Indians, or individual Indians not citizens of the United States.” This contract does not involve noncitizen individual Indians. Therefore, § 81 will apply only if the Tribe is a “tribe of Indians” within the meaning of the statute.
Historically, the federal government has treated a tribe as “recognized” if Congress or the President has created a reservation for the group and the United States has a continuing political relationship with the group. Felix S. Cohen, Handbook of Federal Indian Law 6 (1982). When the tribal status of a group of Indians has been in doubt, the courts have turned to the particular statutory scheme in question to ascertain the rights and responsibilities of the government and the tribe. Id. at 7. Thus, a tribe might be recognized for some purposes and not for others. Id. For example, under the Indian Nonintercourse Act, 25 U.S.C. § 177, which, like 25 U.S.C. § 81 refers to any “tribe of Indians,” the Supreme Court has held that explicit recognition is not required if the group satisfies the general test of tribal status laid out in Montoya v. United States, 180 U.S. 261, 266, 21 S.Ct. 358, 359, 45 L.Ed. 521 (1901). That decision defines a tribe as “a body of Indians of the same or a similar race, united in a community under one leadership or government, and inhabiting a particular though sometimes ill-defined territory.” See United States v. Candelaria, 271 U.S. 432, 442, 46 S.Ct. 561, 563, 70 L.Ed. 1023 (1926). See also Mashpee Tribe v. New Seabury Corp., 592 F.2d 575, 582 (1st Cir.), cert. denied, 444 U.S. 866, 100 S.Ct. 138, 62 L.Ed.2d 90 (1979); Joint Tribal Council of the Passamaquoddy Tribe v. Morton, 528 F.2d 370, 377 n. 8 (1st Cir.1975).
The Western Shoshones argue that by this standard they are a recognized tribe for purposes of 25 U.S.C. § 81. Although they may at one time have been correct in this contention, we conclude that the limited circumstances under which ad hoc judicial determinations of recognition were appropriate have been eclipsed by federal regulation. In 1978, the Department of Interior promulgated regulations establishing “procedures for establishing that an American Indian group exists *1057as an Indian tribe.” 25 C.F.R. pt. 83; see 25 U.S.C. §§ la, 2. The express purpose of these regulations is
to establish a departmental procedure and policy for acknowledging that certain American Indian tribes exist. Such ac-knowledgement of tribal existence by the Department is a prerequisite to the protection, services, and benefits from the Federal Government available to Indian tribes. Such acknowledgement shall also mean that the tribe is entitled to the immunities and privileges available to other federally acknowledged Indian tribes by virtue of their status as Indian tribes as well as the responsibilities and obligations of such tribes.
25 C.F.R. § 83.2. The regulations obligated the Department of the Interior to contact all Indian groups in the continental United States known to it who had not previously been recognized and inform them of the opportunity to obtain recognition. Id. § 83.-6(a). The Department is further required to publish and update a list of all Indian tribes that are recognized and receiving services from the BIA. The Western Shoshones do not appear on the most recent version of that list, 53 Fed.Reg. 52,829-02 (1988).
The judiciary has historically deferred to executive and legislative determinations of tribal recognition. See United States v. Rickeii, 188 U.S. 432, 445, 23 S.Ct. 478, 483, 47 L.Ed. 532 (1903); United States v. Holliday, 70 U.S. (3 Wall.) 407, 419, 18 L.Ed. 182 (1865). Although this deference was originally grounded in the executive’s exclusive power to govern relations with foreign governments, broad congressional power over Indian affairs justifies its continuation. We therefore conclude that the. Tribe’s absence from this list is dispositive. See Edwards, McCoy & Kennedy, 18 I.B.I.A. at 457 (25 C.F.R. pt. 83 procedures “are binding on the Department of the Interior as to which Indian entities may be considered Indian tribes under statutes and regulations which do not define the term ‘Indian tribe.’ ”).
Plaintiffs’ arguments to the contrary are not persuasive. They cite several cases for the proposition that a tribe may not be included on the list of federally recognized tribes and yet still be recognized for purposes of 25 U.S.C. § 81. Many of these cases, however, address the status of Indian groups in Alaska and Hawaii, to which the acknowledgement procedures of 25 C.F.R. § 83 specifically do not apply. Id. § 83.3(a). See Native Village of Tyonek v. Puckett, 957 F.2d 631, 635 (9th Cir.1992) (applying tribal status tests of United States v. Sandoval, 231 U.S. 28, 46-47, 34 S.Ct. 1, 5-6, 58 L.Ed. 107 (1913) and Montoya, 180 U.S. at 266, 21 S.Ct. at 359, to Alaskan Native village); Native Village of Noatak v. Hoffman, 896 F.2d 1157, 1160 (9th Cir.1990) (recognizing Alaskan Native village organized under the Indian Reorganization Act, 25 U.S.C. §§ 461-479, for purposes of jurisdiction under 28 U.S.C. § 1362), rev’d on other grounds, 498 U.S. 807, 111 S.Ct. 37, 112 L.Ed.2d 14 (1990); Price v. Hawaii, 764 F.2d 623, 626-29 (9th Cir.1985) (using regulations regarding ac-knowledgement, as well as other factors, for guidance in determining tribal status of native Hawaiian body), cert. denied, 474 U.S. 1055, 106 S.Ct. 793, 88 L.Ed.2d 771 (1986). Other relatively recent cases in which courts did not defer to the Department’s acknowl-edgement procedures either predate the regulations entirely, see Joint Tribal Council of the Passamaquoddy Tribe v. Morton, 528 F.2d 370 (1st Cir.1975), or were decided only shortly after the regulations were promulgated, see Mashpee Tribe v. New Seabury Corp., 592 F.2d 575, 581 (1st Cir.1979) (“the Department does not yet have prescribed procedures and has not been called on to develop special expertise in distinguishing tribes from other groups of Indians”).
We are strongly persuaded by a similar case, James v. United States Dep’t of Health & Human Services, 824 F.2d 1132 (D.C.Cir.1987). James involved an intra-tribal rivalry between two factions of the Gay Head Indians of Martha’s Vineyard, Massachusetts, which had not been recognized as a tribe when the acknowledgement regulations were first promulgated. One faction, the Widdis group, followed the acknowledgement procedures, filed a petition with the Department of Interior, and was recognized in 1987. The other faction, the James group, contended that the Gay Head Indians had been recog*1058nized at least since the nineteenth century and therefore sought a court order placing the tribe on the Department of Interior’s list of recognized tribes. The D.C. Circuit refused to pass on whether the evidence of historical recognition presented by the James group supported their claim. It reasoned that Congress has specifically authorized the Executive .Branch to regulate Indian affairs, and that the Department of the Interior has developed procedures expressly for determinations of tribal status. “That purpose would be frustrated if the Judicial Branch made initial determinations of whether groups have been recognized previously or whether conditions for recognition currently exist.” Id. at 1137. The court further took note of the Mashpee decision and observed that the Department has been implementing these regulations for several years and now has the necessary expertise to make tribal status determinations in the first instance. Id. at 1138.
Because the Western Shoshones do not appear on the Department of Interior’s list of recognized tribes, the Council is not within the zone of interests of § 81 and does not have standing to bring this suit.4
Ill
Plaintiffs have asserted various other bases for jurisdiction under which they might also have standing, which we address briefly. They claim that jurisdiction is proper under 28 U.S.C. § 1331 (federal question), 28 U.S.C. § 1346(a)(2) (United States as a defendant), 28 U.S.C. § 1361 (mandamus), and 28 U.S.C. § 1362 (actions by Indian Tribes).
For this court to exercise federal question jurisdiction under 28 U.S.C. § 1331, there must be a constitutional or federal statutory provision under which plaintiffs are aggrieved. See Gully v. First Nat’l Bank, 299 U.S. 109, 112, 57 S.Ct. 96, 97, 81 L.Ed. 70 (1936) (“To bring a case within [§ 1331], a right or immunity created by the Constitution or laws of the United.States must be an element, and an essential one, of the plaintiffs cause of action.”). Although plaintiffs maintain that their complaint stems from the contract approval procedure of 25 U.S.C. § 81, we have already held plaintiffs are not within the compass of that statute for judicial redress until there is a determination of their status under the regulations governing tribal recognition. That section 81 authorizes suits in the name of the United States to recover sums paid under contracts which do not comply with its provisions does not amount to “arising under” jurisdiction for all complaints involving this section. See, e.g., Gila River Indian Community v. Henningson, Durham & Richardson, 626 F.2d 708, 714-15 (9th Cir.1980), cert. denied, 451 U.S. 911, 101 S.Ct. 1983, 68 L.Ed.2d 301 (1981); Mescalero Apache Tribe v. Martinez, 519 F.2d 479, 481-82 (10th Cir.1975).
Plaintiffs invoke 28 U.S.C. § 1362, which specifically grants district courts jurisdiction in federal question cases brought by Indian tribes.5 Although § 1362 clearly removed some jurisdictional impediments for Indian tribes, see Moe v. Confederated Salish & Kootenai Tribes of the Flathead Reservation, 425 U.S. 463, 472-73, 96 S.Ct. 1634, 1640-41, 48 L.Ed.2d 96 (1976), it did not eliminate the requirement that there be a statutory or constitutional underpinning for the cause of action. See Gila River, 626 F.2d at 714 (“Congress used ‘arising under’ language in section 1362 that is identical to that contained in section 1331.”); see also Oneida Indian Nation v. County of Oneida, 414 U.S. 661, 682 n. 16, 94 S.Ct. 772, 784 n. 16, 39 L.Ed.2d 73 (1974) (declining to find § 1362 broader than § 1331). For the same reasons *1059that plaintiffs cannot bring this action under § 1331, they also cannot assert jurisdiction under § 1362.
Section 1346 of Title 28 grants jurisdiction over certain suits against the United States to the district courts. However, it does not waive the government’s sovereign immunity. It is well settled that the United States and its employees, sued in their official capacities, are immune from suit unless sovereign immunity has been waived. Atkinson v. O’Neill, 867 F.2d 589, 590 (10th Cir. 1989). Plaintiffs do not allege to any express waiver of immunity in this case.
Plaintiffs also seek a writ of mandamus under 28 U.S.C. § 1361. Mandamus is a drastic remedy, available only in extraordinary circumstances. Allied Chemical Corp. v. Daiflon, Inc., 449 U.S. 33, 34-35, 101 5.Ct. 188, 189-90, 66 L.Ed.2d 193 (1980). Furthermore, the writ is not available when review by other means is possible. Ketr v. United States District Court, 426 U.S. 394, 403, 96 S.Ct. 2119, 2124, 48 L.Ed.2d 725 (1976). Because review is possible under the APA after plaintiffs have followed the procedures of 25 C.F.R. pt. 83, mandamus is not available.
IV
We turn now to plaintiffs’ contention that the district court should have granted them leave to amend their complaint. After final judgment was entered, plaintiffs sought to amend their complaint to require the Secretary of the Interior to place the Western Shoshones on the list of recognized tribes, and to add an individual Indian plaintiff and allege a claim under 25 U.S.C. § 85.6 Once final judgment is entered, plaintiffs must seek leave of the court to file an amended complaint. Cooper v. Shumway, 780 F.2d 27, 29 (10th Cir.1985). We review the district court’s denial of such leave for an abuse of discretion. Stichting Mayflower Recreational Fonds v. Newpark Resources, Inc., 917 F.2d 1239, 1249 (10th Cir.1990).
The district court struck the amended complaint, concluding that 25 U.S.C. § 85 would not provide relief when the contract in question obligated only the tribe and not any individual Indian. It further observed that requiring the Secretary to place the Western Shoshones on the list of recognized tribes simply restated the issues contained in the original complaint and would not cure the complaint’s defects. We agree with these conclusions. The district court did not abuse its discretion in denying the amendment.
AFFIRMED.
. In pertinent part, 25 U.S.C. § 81 provides:
No agreement shall be made by any person with any tribe of Indians ... for the payment or delivery of any money or other thing of value, in present or in prospective, or for the granting or procuring any privilege to him, or any other person in consideration of services for said Indians relative to their lands ... unless such contract or agreement be executed an approved as follows:
Second. It shall bear the approval of the Secretary of the Interior and the Commissioner of Indian Affairs indorsed upon it.
Section 81 docs not contain a definition of "tribe of Indians."
. The Shoshone-Paiute Tribes of the Duck Valley Reservation is on the list of recognized tribes and receives services and benefits from the BIA. The Shoshone-Paiute Tribes is a confederation of the Western Shoshones and the Paddy Cap Band of Paiutes, who have resided together in the Duck Valley region for over one hundred years. It is organized under the Indian Reorganization Act, 25 U.S.C. §§ 461-479, with a constitution and bylaws approved by the Secretary of the Interior.
. In keeping with the recent Supreme Court decision discussing administrative exhaustion, Darby v. Cisneros, — U.S. -, 113 S.Ct. 2539, 125 L.Ed.2d 113 (1993), we note that the Department of the Interior decisions are not final for purposes of § 704 review if they are subject to appeal to a higher authority within the department. 25 C.F.R. § 2.6(a).
. Plaintiffs argue that they should not be required to pursue the recognition procedures outlined in 25 C.F.R. pt. 83 before bringing this suit because it would take too long, the Council would be deprived of legal services during the delay, and the Western Shoshones' recognition as a tribe is a matter of simple statutory construction. We reject these arguments because plaintiffs cannot claim the administrative process is inadequate until they attempt to invoke it.
. 28 U.S.C. § 1362 provides: "The district courts shall have original jurisdiction of all civil actions, brought by any Indian tribe or band with a governing body duly recognized by the Secretary of the Interior, wherein the matter in controversy arises under the Constitution, laws, or treaties of the United States.” Here we assume for argument’s sake that the Western Shoshones are an Indian tribe within the meaning of this statute.
. 25 U.S.C. § 85 provides:
No contract made with any Indian, where such contract relates to the tribal funds or property in the hands of the United States, shall be valid, nor shall any payment for services rendered in relation thereto be made unless the consent of the United States has previously been given.