Sachverhalt: A. A.a Mit Bundesgesetz vom 13. Juni 2008 über die Neuordnung der Pflegefinanzierung wurde u.a. ein neuer Art. 25a KVG eingeführt, welcher die Pflegeleistungen bei Krankheit regelt. Danach leistet die obligatorische Krankenpflegeversicherung einen vom Bundesrat festzulegenden Beitrag an die Pflegeleistungen (Abs. 1, 3 und 4). Von den nicht von Sozialversicherungen gedeckten Pflegekosten dürfen der versicherten Person höchstens 20 Prozent des höchsten vom Bundesrat festgesetzten Pflegebeitrags überwälzt werden (Abs. 5 Satz 1). Die Kantone regeln die Restfinanzierung (Abs. 5 Satz 2). Die Gesetzesänderung trat am 1. Januar 2011 in Kraft. A.b Zur Umsetzung der neuen Pflegefinanzierung erliess der Regierungsrat des Kantons Basel-Stadt am 23. November 2010 eine Änderung der Verordnung über die Krankenversicherung im Kanton Basel-Stadt vom 25. November 2008 (KVO/BS; Syst. Nr. 834.410). Diese Änderung wurde am 27. November 2010 im Kantonsblatt publiziert und auf den 1. Januar 2011 in Kraft gesetzt. Sie enthält u.a. einen neuen § 8d mit dem Titel "Restfinanzierung durch den Kanton in Anwendung von Art. 25a Abs. 5 KVG". Abs. 1 enthält für jede der zwölf Pflegestufen (vgl. Art. 7a Abs. 3 der Krankenpflege-Leistungsverordnung vom 29. September 1995 [KLV; SR 832.112.31]) die Pflegekosten pro Tag. Gemäss Abs. 2 entspricht die Höhe der Restfinanzierung der Differenz zwischen den anerkannten Pflegekosten und den Leistungen der Krankenversicherer gemäss Art. 7a KLV sowie dem maximalen Eigenbeitrag der versicherten Person gemäss § 8. In der Folge lautet § 8d Abs. 4 KVO/BS sodann: "Für die Erfassung des Pflegebedarfs der Bewohnerinnen und Bewohner gilt für die Pflegeheime, welche auf der kantonalen Pflegeheimliste aufgeführt sind, das Bedarfserfassungssystem RAI/RUG in der Version CH-Index 2011 (Anhang)." Anhang 1 führt Folgendes aus: Pflegestufe Pflegeaufwand in Minuten pro Tag CH-Index 2011 Original-RUG's 1 bis 20 0.095 PA0 2 21-40 0.285 PA1 3 41-60 0.476 BA1, PA2 4 61-80 0.666 IA1, BA2 5 81-100 0.856 PB1, PB2, BB1 6 101-120 1.046 CA1, IB1, PC1, BB2, PC2 7 121-140 1.237 IA2, IB2, CA2 8 141-160 1.427 PD1, PD2, CB1, RMA, RLA 9 161-180 1.617 CB2, SSA, RMB, CC1 10 181-200 1.807 SSB, PE1, RLB, CC2, PE2 11 201-220 1.998 SSC, SE1 12 ab 221 2.188 RMC, SE2, SE3 B. Am 6. Dezember 2010 erhoben der Verein santésuisse sowie 81 Krankenversicherer gemeinsam Beschwerde beim Appellationsgericht des Kantons Basel-Stadt (als Verfassungsgericht) mit dem Antrag, § 8d Abs. 4 sowie der entsprechende Anhang KVO/BS gemäss Teilrevision vom 23./27. November 2010 seien aufzuheben. Mit Urteil vom 17. Februar 2012 wies das Appellationsgericht die Beschwerde ab. C. Der Verein santésuisse sowie 79 der vorinstanzlich beteiligten Krankenversicherer erheben Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, das angefochtene Urteil sei aufzuheben und § 8d Abs. 4 KVO/BS samt Anhang sei als bundesrechtswidrig und ungültig zu erklären. Eventuell sei die Sache an die Vorinstanz zurückzuweisen. Das Appellationsgericht und das Gesundheitsdepartement des Kantons Basel-Stadt (in Vertretung des Regierungsrates) beantragen Abweisung der Beschwerde. Das Bundesamt für Gesundheit beantragt Gutheissung der Beschwerde und Zurückweisung an das Appellationsgericht. Die Beschwerdeführer äussern sich mit Stellungnahme vom 8. Oktober 2012 zu den eingegangenen Vernehmlassungen. 