BRISCOE, Circuit Judge.
Plaintiffs Kane County, Utah, the Kane County Board of Commissioners, Garfield County, Utah, the Garfield County Board of Commissioners, and the Kane County Water Conservancy District filed suit against the Secretary of the Interior and other federal governmental officials alleging that a management plan adopted by defendants for overseeing the Grand Staircase-Escalante National Monument infringed upon plaintiffs’ water rights and certain rights-of-way utilized by plaintiffs [1079] for purposes of public highways. The district court dismissed plaintiffs’ claims pursuant to Federal Rule of Civil Procedure 12(b)(1) and (6). Plaintiffs now appeal. We exercise jurisdiction pursuant to 28 U.S.C. § 1291 and affirm.
I
Rights-of-way over public lands pursuant to R.S. 21.77
“In 1866, Congress passed an open-ended grant of ‘the right of way for the construction of highways over public lands, not reserved for public uses.’” S. Utah Wilderness Alliance v. Bureau of Land Mgmt., 425 F.3d 735, 740 (10th Cir.2005) (quoting Act of July 26, 1866, ch. 262, § 8, 14 Stat. 251, 253, codified at 43 U.S.C. § 932, repealed by Federal Land Policy Management Act of 1976 (FLPMA), Pub.L. No. 94-579 § 706(a), 90 Stat. 2743). “This statute, commonly called ‘R. S. 2477,’ remained in effect for 110 years, and most of the transportation routes of the West were established under its authority.” Id. “In 1976, however, Congress abandoned its prior approach to public lands and instituted a preference for retention of the lands in federal ownership, with an increased emphasis on conservation and preservation.” Id. at 741. “As part of that statutory sea change, Congress repealed R.S. 2477.” Id. “There could be no new R.S. 2477 rights of way after 1976.” Id. “But even as Congress repealed R.S. 2477, it specified that any ‘valid’ R.S. 2477 rights of way ‘existing on the date of approval of th[e] [FLPMA]’ (October 21, 1976) would continue in effect.” Id. (quoting Pub.L. No. 94-579 § 701(a), 90 Stat. 2743, 2786 (1976)). Congress also directed that “[a]ll actions [taken] by the Secretary concerned under this Act [the FLPMA] shall be subject to valid existing rights.” 43 U.S.C. § 1701 historical note (h).
Creation of the Monument
On September 18, 1996, President Clinton created the Grand Staircase-Escalante National Monument (Monument), located in Kane and Garfield Counties, Utah, to protect a “spectacular array of scientific and historic resources.” 61 Fed.Reg. 50,-223 (Sept. 18, 1996). In doing so, President Clinton proclaimed that “[a]ll Federal lands and interests in lands within the boundaries of th[e] monument [we]re [tjhereby appropriated and withdrawn from entry, location, selection, sale, leasing, or other disposition under the public land laws,” and that “[l]ands and interests in land not owned by the United States s[hould] be reserved as a part of the monument upon acquisition of title thereto by the United States.” Id. at 50,225. The proclamation did not, however, “reserve water as a matter of Federal law.” Id. As part of the proclamation, President Clinton directed the Secretary of the Interior (the Secretary) to “prepare, within 3 years ..., a management plan for” the Monument. Id. Lastly, the proclamation provided that the Secretary would “manage the [Monument through the Bureau of Land Management” (BLM). Id.
The management plan for the Monument
On November 15, 1999, the Secretary issued a final management plan (the Plan) and record of decision (ROD) for the Monument. 65 Fed.Reg. 10,819 (Feb. 29, 2000).
The ROD, which was published as part of the Plan, stated, in pertinent part:
[Djiscussion of R.S. 2477 assertions in footnote 1 of Chapter 2 of the Approved Plan has also been clarified to emphasize that nothing in the Plan extinguishes any valid existing rights-of-way in Grand Staircase-Escalante National Monument. Nothing in this Plan alters in any way any legal rights the Counties of [1080] Garfield and Kane or the State of Utah has to assert and protect R.S. 2477 rights, and to challenge in Federal court, or any other appropriate venue, any BLM road closures that they believe are inconsistent with their rights.
App. at 20 (citing ROD, p. ix).
The Plan, in a section entitled Transportation and Access, stated:
TRAN-1 This Plan designates the route system for the Monument. The transportation map (Map 2, in the back of the document) shows routes that will be open for public use and those available for administrative use only (see the Administrative Routes and Authorized Users section for related decisions). Any route not shown on Map 2 is considered closed upon approval of this Plan, subject to valid existing rights. [fn.1]
The specific routes shown open for public use are based on a variety of considerations including what is needed to protect Monument resources, implement the planning decisions, and provide for the transportation needs of surrounding communities. The basic philosophy in determining which routes will be open was to determine which routes access some destinations (e.g., scenic overlook, popular camping site, heavily used thoroughfare) and present no significant threat to Monument resources. These routes will be open for public use. Routes that were not considered necessary or desirable (for resource protection purposes) will not be kept open for motorized and mechanized public access. In the event that Title 5 rights-of-way are issued or in the event of legal decisions on RS 2^77 assertions, routes will he governed under the terms of those actions.
Grand Staircase-Escalante National Monument Management Plan at 46, available at http://www.blm.gov/ut/st/en/fo/grand_ staircase-escalante/planning/monument_ management.html (last visited on January 20, 2009) (emphasis added).1
Under the Transportation and Access provisions, the Plan also provided:
Road Restoration Strategy
TRAN-17 The BLM’s strategy for restoring routes that will no longer be available for public or administrative [1081] motorized use in the Monument will be phased over a period of years. This will be accomplished as rapidly as funding permits. It is anticipated that this could take as many as ten years. Each year, a percentage of the Monument’s base budget will be used to restore routes in areas that are easily accessible to the public and that involve sensitive resources in immediate danger of being degraded. Generally, routes in the Frontcountry and Passage Zones will be closed first. However, there may be routes in the Outback and Primitive Zones that will be considered on a case-by-case basis.
The proposal for restoration will include:
• not repairing washed out routes
• natural barriers, such as large boulders
• dead and down wood to obscure route entry ways
• fences
• ripping up the route bed and reseeding with vegetation natural to that area
• replacing gates with a fence if area has a fence in place
• visitor education and information
Each route will be looked at individually, and the best, least intrusive method will be used based on the geography, topography, soils, hydrology, and vegetation. The first several hundred feet of select routes identified for closure could be left open to provide pull-out areas or camping opportunities, preventing new ground disturbance elsewhere.
Id. at 48.
The Plan also addressed the diversion of water to locations outside of the Monument:
Water
WAT-1 Ensure that land management policies protect water resources.
Since much of the water important to the Monument falls as precipitation within the Monument, its continued availability can be ensured by appropriate land management policies within the Monument. The BLM will exercise its existing land management authorities to protect and maintain all available water and natural flows in the Monument. Several decisions described in other sections of this Plan are designed to meet this objective. These include the following:
• In general, diversions of water out of the Monument will not be permitted. There is an existing small-scale diversion of groundwater out of the Monument for the domestic water supply of the nearby town of Henrieville. This Plan does not prohibit the continuation of this diversion, nor its expansion, if necessary, to meet the municipal needs of population growth in Henrieville. Any proposed new groundwater diversion to meet Henrieville’s municipal needs could be approved, consistent with the Plan, if the BLM and the Utah State Engineer complete a joint analysis to determine that such development would not adversely impact springs or other water resources within the Monument, and the BLM completes the usual NEPA analysis. Exceptions could be considered for other local community culinary needs if the applicant could demonstrate that the diversion of water will not damage water resources within the Monument or conflict with the objectives of this Plan.
Id. at 31-32 (italics in original).
The filing and dismissal of plaintiffs’ complaint
On November 14, 2005, a group of entities consisting of Kane County, Utah, the [1082] Kane County Board of Commissioners, the Kane County Water Conservancy District (the District), Garfield County, Utah, and the Garfield County Board of Commissioners filed this action against the Secretary, the Department of the Interior, the BLM and its Director, the acting Utah State Director of the BLM, and the Manager of the Monument, seeking mandamus, declaratory and injunctive relief. In their first amended complaint, the plaintiffs alleged that Kane and Garfield Counties “own[ed] ... numerous R.S. 2477 rights-of-way crossing public lands within the Counties and also within the Monument” “that continue[d] to serve the valuable interests of the public in traveling from place to place across public lands within and without [the] Counties,” App. at 15, and that the Counties were authorized under Utah state law to regulate the use of the roads on, and traffic across, those rights-of-way, id. at 16. The first amended complaint further alleged that the District “own[ed] various water rights and rights to water within Kane County,” id. at 17, “some of which ha[d] points of diversion within the boundaries of the Monument,” id. at 18. In turn, the first amended complaint alleged that the Plan “fail[ed] to comply with” the FLPMA “in that it [wa]s not subject to valid existing rights, it restricted] the use of, and terminate[d], valid existing rights, it extensively and unnecessarily curtailed] historic and current public uses, it utterly fail[ed] to address Plaintiffs’ local plans, and it ignore[d] FLPMA’s principles of multiple use.” Id. at 24-25. More specifically, the first amended complaint alleged that the Plan and/or its implementation:
• “created a transportation system in willful blindness to [the] Counties’ prior-existing rights, purported to regulate and restrict the use of valid existing rights, and to otherwise close and destroy valid existing rights within the boundaries of the Monument,” id. at 25;
• “fail[ed] to identify even a single county right-of-way within the entire 1.8 million acre Monument,” id.;
• “denied and impaired [the] Counties’ ability to manage their rights-of-way, the public's historic uses and rights, and the county roads that traverse these rights-of-way in accordance with applicable law,” id. at 25-26;
• “denied [the] Counties, and the public, the use and enjoyment of the Counties’ rights-of-way within the Monument, including according to historic and current public uses,” id. at 26; and
• “purported] to trap the District’s water rights and points of diversion within the Monument, and to impose unauthorized burdens upon the District to seek diversion of these water rights from the Monument,” id. at 27.
Based upon these allegations, the first amended complaint asserted three causes of action against defendants: (1) a claim under the Administrative Procedures Act (APA) and/or “the doctrine of non-statutory judicial review,” id. at 28, seeking a declaration that defendants’ actions had violated the FLPMA and/or the Due Process Clause and impaired the Counties’ “interests in the continuing use, access, possession, maintenance and management of their rights-of-way,” id. at 29; (2) a claim for injunctive relief in the form of “an order ... enjoining enforcement of [certain] Transportation and Access, including Map 2, LAND-4, and Water sections of the Plan,” id. at 30; and (3) a claim for mandamus relief in the form of a court order “directing each of the Individual Defendants to first determine Plaintiffs’ valid existing rights before asserting or taking any action in enforcement or implementation of [certain] Transportation and Access, including Map 2, LAND-4, or [1083] Water sections of the Plan,” and “directing Monument manager David Hunsaker to remove any physical barriers placed upon any right-of-way or road within the Monument until such time as it has been determined that such actions will not impair valid existing rights,” id. at 31.
On November 23, 2005, the Southern Utah Wilderness Alliance, the National Trust for Historic Preservation, The Wilderness Society, and the Sierra Club (collectively SUWA) moved to intervene as defendants in the action pursuant to Fed. R.Civ.P. 24(a)(2). The district court granted SUWA’s motion on January 5, 2006.
On May 5, 2006, the federal defendants moved to dismiss the first amended complaint on four grounds: (1) “because Plaintiffs’ vague and conclusory assertions of injuries to unspecified rights-of-way and water rights [we]re insufficient to establish a concrete, injury-in-fact giving rise to standing,” id. at 53; (2) “because Plaintiffs’ challenges to the Plan [wejre not ripe due to Plaintiffs’ failure to allege how the Plan ha[d], in fact, restricted or denied on a site-specific level the exercise of any valid existing rights held by Plaintiffs,” id. at 54; (3) “because the APA does not waive sovereign immunity for the adjudication of claims that are premised upon the assertion of unproven property interests in federal land, such as Plaintiffs’ right-of-way and water right claims,” id.; and (4) “because neither FLPMA nor the Due Process Clause require[d] the Federal Defendants to identify and determine all existing rights-of-way within a planning area when preparing a land use plan,” id.
On May 25, 2006, SUWA moved for judgment on the pleadings, arguing, in pertinent part, that “the United States [could] not be sued based upon bare allegations of title, such as made by the Counties here, except under the Quiet Title Act, 28 U.S.C. § 2409a, which the Counties failed to invoke.” Id. at 111.
On June 29, 2007, the district court issued a memorandum opinion and order granting in part the federal defendants’ motion to dismiss and SUWA’s motion for judgment on the pleadings. In doing so, the district court dismissed the claim for judicial review of the Plan under the APA, but granted the plaintiffs leave to file an amended complaint under the Quiet Title Act “as to the existence and scope of R.S. 2477 rights-of-way....” Id. at 446. As for the “District’s claim concerning the diversion of water out of the Monument,” the district court dismissed it “as premature,” but granted the District “leave to file an amended complaint within twenty (20) days....” Id.
The District’s supplement to the first amended complaint
On July 16, 2007, the District filed a supplement to the first amended complaint. The supplement alleged that “on June 5, 2006 ..., the District filed its Application for Transportation and Utility Systems and Facilities on Federal Lands ... for the purpose of obtaining a right-of-way for the use of a well-pad and to install a 12" to 14" buried pipeline and related utility lines along an existing road.” Id. at 450-51. The supplement further alleged that “[t]he Monument manager[ ]” responded to the Application by citing the Plan provisions regarding diversions of water and stating that a right-of-way “could probably be issued,” id. at 453, if the District was able to demonstrate “that the diversion of water w[ould] not damage water resources within the Monument or conflict with the objectives of th[e] Plan,” id. at 452. The supplement alleged that “[d]efendants ha[d] no right or authority to determine underground water resource damage, water conflicts, or to prohibit [1084] types of uses of the District’s water” because “[t]hose decisions [we]re within the exclusive jurisdiction of the Utah State Engineer.” Id. at 453. In addition, the supplement alleged that “[djefendants ha[d] no process or authority for adjudicating water resource damage or conflicts, nor any such process or authority for the ‘criteria’ that [wejre ... being imposed upon the District” by the Monument manager and his staff. Id. at 454. Ultimately, the supplement alleged that “[djefendants’ refusal to process the District’s Application ... constitute^] [either] discrete, final agency action that [wa]s arbitrary, capricious and beyond statutory right and authority,” id., or “agency action unlawfully withheld or unreasonably delayed,” id. at 455. In turn, the supplement asked the district court to “enter an order declaring the water resource based restrictions or criteria on diversion of water from the Monument in the Plan’s LAND^i and WAT-2 sections to be arbitrary, capricious, or beyond right or authority,” “enjoining enforcement of the unlawful water resource based restrictions or criteria in the Plan’s LAND-4 and WAT-2 sections,” and “directing defendants to process the District’s application without reference to the unlawful restrictions or criteria....” Id.
On August 2, 2007, the federal defendants moved to dismiss the first amended complaint as supplemented by the District. The motion argued that the supplement “should be dismissed as unripe and for lack of subject matter jurisdiction because the Plan d[id] not prohibit new water diversions within the Monument and the District otherwise c[ould not] establish that the BLM ha[d] denied or unreasonably delayed the processing of the [District’s] Application.” Id. at 487. In the memorandum in support of the motion, the federal defendants acknowledged that the District had filed its Application on June 5, 2006. The federal defendants alleged, however, that the Monument manager notified the District on June 26, 2006, “that additional information and documentation [including a location map] needed to be submitted before the Application could be processed.” Id. at 495. The Monument manager allegedly further advised the District that (a) the processing time would vary depending upon whether the District or the BLM prepared the environmental assessment (EA), (b) there were no restrictions in the Plan that would preclude issuance of the right-of-way (assuming the District could establish that the diversion of water would not damage water resources within the Monument or conflict with the objectives of the Plan), and (e) it would be premature to offer any opinion on the likelihood that the Application would be approved. Id. at 496. According to the federal defendants, the District subsequently completed its Application and the Monument Manager, on July 31, 2007, sent a letter to the District advising it “that upon payment of the required processing fee, the BLM w[ould] begin processing the Application and preparing an [EA] to analyze the action....” Id. at 498. Based upon these allegations, the federal defendants’ motion argued that the District’s challenges to the water provisions of the Plan were unripe and should be dismissed for lack of subject matter jurisdiction.
On August 24, 2007, SUWA filed a motion for judgment on the pleadings arguing that, “for the reasons set forth in the” federal defendants’ motion to dismiss, the District’s supplemental complaint should “be dismissed for lack of ripeness and failure to state a claim upon which relief c[ould] be granted.” Id. at 550.
On December 19, 2007, the district court issued an order granting the federal defendants’ motion to dismiss and SUWA’s mo[1085] tion for judgment on the pleadings. Id. at 711. In doing so, the district court opined “that the District’s claims [we]re still premature” because its “Application [wa]s still pending before the BLM,” id. at 713, and “the Utah State Engineer ha[d] not taken any final action on a separate water right change application filed by the District with the State Engineer in August, 2007,” id. at 714. In short, the district court noted that “not much ha[d] changed since the Court issued its Memorandum Opinion, and the District’s challenges to the water provisions of the Plan remain[ed] unripe and premature pursuant to the terms of the Court’s prior ruling.” Id.
The District has since filed a timely notice of appeal from the district court’s June 29, 2007, and December 19, 2007, orders.
The County plaintiffs’ appeal
On July 31, 2007, the County plaintiffs (all of the plaintiffs except for the District) filed a motion asking the district court to certify, pursuant to Fed.R.Civ.P. 54(b), “its Memorandum Opinion and Order dated June 29, 2007 as a final order.” Id. at 472. On September 27, 2007, before any action was taken on their Rule 54(b) motion, the County plaintiffs filed a notice of appeal from the district court’s memorandum opinion and order entered on June 29, 2007, dismissing their claims. Shortly thereafter, the district court issued a memorandum opinion and order granting the County plaintiffs’ Rule 54(b) motion.2 Id. at 683.
Consolidation of appeals
On February 4, 2008, we issued an order consolidating the two appeals “for purposes of record creation, briefing, and court consideration.” Id. at 718.
II
Appeal No. 07-4207
The County plaintiffs, in Appeal No. 07-4207, contend the district court erred in granting the federal defendants’ motion to dismiss and SUWA’s motion for judgment on the pleadings. “We review a district court’s dismissal for lack of subject matter jurisdiction under Fed.R.Civ.P. 12(b)(1) de novo.” Tsosie v. United States, 452 F.3d 1161, 1163 (10th Cir.2006). “A district court’s dismissal for failure to state a claim under Fed.R.Civ.P. 12(b)(6) is also reviewed de novo.” Id.
1) Did the district court’s summary dismissal violate Olenhouse?
The County plaintiffs first assert that the district court’s summary dismissal of their claims, i.e., dismissing based solely on review of the first amended complaint and motions, and without benefit of the administrative record, violated the procedures required by our decision in Olen-house v. Commodity Credit Corp., 42 F.3d 1560 (10th Cir.1994). According to the County plaintiffs, the allegations of their first amended complaint established that they had both constitutional and prudential standing to challenge the BLM’s Plan, and thus the district court was prohibited from summarily dismissing their complaint, and was instead required to obtain the administrative record and review on the merits the challenged agency action.
We readily reject the County plaintiffs’ arguments. It is true that in Olen-[1086] house we outlined the principles of judicial review of final agency action under the Administrative Procedure Act (APA), 5 U.S.C. § 706. See 42 F.3d at 1573-74. Importantly, however, nothing in Olen-house (or, for that matter, other controlling case law or the APA itself) precludes an APA-based complaint from being summarily dismissed pursuant to Federal Rule of Civil Procedure 12(b). Indeed, Olen-house is silent with respect to the propriety of motions to dismiss APA-based claims.3 Olenhouse aside, case law firmly establishes that APA-based claims can, if appropriate, be summarily dismissed. E.g., Benzman v. Whitman, 523 F.3d 119, 132 (2d Cir.2008) (concluding that district court “properly rejected the sufficiency of all aspects of the Plaintiffs’ non-constitutional APA claims”).
We thus conclude, contrary to the County plaintiffs’ arguments, that the district court did not err by dismissing the complaint pursuant to Rule 12(b) and without obtaining or reviewing the administrative record.
2) Did the district court properly dismiss the County plaintiffs’ claims?
The County plaintiffs assert a host of challenges to the merits of the district court’s order dismissing their claims. Chief among those is their contention that the federal defendants have a duty, prior to closing or managing any roads on purported R.S. 2477 rights-of-way, to conduct administrative determinations regarding the validity of those purported rights-of-way. Id. at 38. “These determinations,” the County plaintiffs argue, “are necessary for the Federal Defendants to comply with their FLPMA duty to manage public lands ‘subject to valid existing rights’ and without diminishing or reducing any right-of-way granted prior to 1976.” Id. at 38-39. We disagree.
Prior to 1994, “the BLM staunchly maintained that it lacked authority to make binding decisions on R.S. 2477 rights of way.” S. Utah, 425 F.3d at 754. “In 1994,” however, “the BLM changed course and proposed comprehensive regulations governing R.S. 2477 rights of way,” including “an administrative procedure by which the BLM would adjudicate the validity of R.S. 2477 claims.” Id. at 756. “Congress responded with an appropriations provision prohibiting the Department of the Interior from issuing final rules governing R.S. 2477....” Id. “The General Accounting Office has [since] concluded that this provision has the status of permanent law.” Id. (citing GAO Opinion B0277719 at 1-5 (Aug. 20, 1997)). Consequently, we have held “that the BLM lacks primary jurisdiction” to conclusively adjudicate R. S. 2477 claims (such as those now asserted by the County plaintiffs). Id. at 757.
In light of this background, we readily conclude that the County plaintiffs’ allegations failed to state a claim upon which relief could be granted under the APA. Section 706(1) of the APA empowers a district court to “compel agency action unlawfully withheld or unreasonably delayed!.]” 5 U.S.C. § 706(1). In Norton v. S. Utah Wilderness Alliance, 542 U.S. 55, 64, 124 S.Ct. 2373, 159 L.Ed.2d 137 (2004), the Supreme Court held that “a claim under § 706(1) can proceed only where a plaintiff asserts that an agency failed to take a discrete agency action that it is required to take." Here, as noted, we have expressly held, in recognition of bind[1087] ing federal law, that the BLM lacks the authority to conclusively resolve R.S. 2477 claims. S. Utah, 425 F.3d at 757. Thus, the County plaintiffs are not entitled under the APA to an order directing the BLM to resolve all outstanding R.S. 2477 claims as part of its Plan.
In their appellate brief, the County plaintiffs attempt to disclaim any interest in having the BLM conclusively “adjudicate ownership” of the purported R.S. 2477 rights-of-way. Aplt. Br. at 42. According to the County plaintiffs, all they are seeking instead is an order directing the BLM to “consider,” for its own planning purposes, whether or not the County plaintiffs’ purported R.S. 2477 rights-of-way are valid. Id. at 41. More specifically, the County plaintiffs allege that the BLM has a duty to administratively adjudicate, by relying at least in part on “preliminary determinfations]” it made “during its prior [pre-Plan and pre-R. Utah ] transportation planning, any and all R.S. 2477 claims the County plaintiffs may have.” Id. at 45. In our view, however, neither the statute, 43 U.S.C. § 1701 note (providing that “all actions by the Secretary concerned under this Act shall be subject to valid existing rights”), nor the regulation, 43 C.F.R. § 2801.4 (2000)