Faits: A. Dans le canton de Genève, il incombe au Conseil d'Etat de fixer, par voie réglementaire, les mesures nécessaires à la promotion de la qualité de la vendange et des appellations d'origine, après avoir consulté l'Interprofession (cf. art. 20 al. 1 de la loi genevoise du 17 mars 2000 sur la viticulture [LVit; RS/GE M 2 50]). Le Conseil d'Etat a ainsi édicté le règlement du 28 juin 2000 sur les vins genevois (RVins; RS/GE M 2 50.04). Selon l'art. 2 RVins, le règlement s'applique à toute production issue de vignes à vocation vinicole commerciale, situées sur le territoire du canton et recensées dans le cadastre viticole. Aux termes de l'art. 27 RVins, seuls les vins issus des vignes destinées à la production vinicole commerciale et situées dans le cadastre viticole ont droit, lorsque la limitation de rendement à l'unité de surface et les conditions fixées dans le règlement sont respectées, aux appellations suivantes: a) AOC Premier Cru, b) AOC communale et régionale, c) AOC Genève. La disposition transitoire de l'art. 69 RVins règle notamment le cas des vignes situées en zone frontalière. Par règlement du 2 juin 2008, publié dans la Feuille d'avis officielle de la République et canton de Genève du 9 juin suivant, le Conseil d'Etat a modifié l'art. 69 al. 2 RVins. La nouvelle teneur de la disposition est la suivante: " Vins issus de vignes situées en zone frontalière 2 Jusqu'au 31 décembre 2009, les vins issus des vignes situées dans la zone frontalière, dont les propriétaires ou usufruitiers sont domiciliés en Suisse, au sens de la loi fédérale sur les douanes, du 1er octobre 1925, peuvent : a) bénéficier de l'appellation d'origine contrôlée Genève, pour autant qu'ils respectent, en particulier, les exigences prévues pour cette appellation figurant dans le titre III, chapitre I, du présent règlement, dont les autres dispositions sont applicables pour le surplus; b) bénéficier d'une indication de provenance (catégorie II) ou d'une désignation vin blanc, vin rouge (catégorie III), pour autant qu'ils respectent, en particulier, les exigences prévues dans le titre III, chapitre II, du présent règlement, dont les autres dispositions sont applicables pour le surplus." Dans l'exposé des motifs relatif à cette modification, le Conseil d'Etat a expliqué que les frontières du canton de Genève divisaient le bassin agricole naturel de la région genevoise et que, pour remédier à ce problème et assurer l'approvisionnement de Genève, la création d'une zone franche avait accompagné la délimitation des frontières de 1815. Les vignes de zone, appellation non officielle donnée aux vignes com- prises dans un périmètre de 10 km au-delà de la frontière suisse, représentaient une surface de vignes françaises d'environ 130 hectares, dont le raisin était vinifié en Suisse. Jusqu'au 31 décembre 2007, la production issue de ces vignes pouvait prétendre à l'appellation d'origine (AO) Genève dans la mesure où le propriétaire était domicilié en Suisse. Une remise en cause importante de ce statut était apparue à la suite de l'adoption en 1999 de l'Accord bilatéral entre la Suisse et la Communauté européenne. En effet, l'annexe consacrée aux produits viti-vinicoles prévoyait qu'un vin suisse devait résulter d'un processus de transformation réalisé sur territoire suisse à partir de raisins récoltés sur ce même territoire. La définition des vins français était fondée sur la même logique. En conséquence, les vins issus des vignes de zone et vinifiés en Suisse étaient devenus des vins apatrides, ni suisses ni français. De surcroît, le régime des AO avait été aboli en Suisse depuis le 1er janvier 2008. Un projet de modification de l'Accord bilatéral était en cours, qui permettrait d'étendre l'AOC Genève sur le territoire français. Dans l'attente de son entrée en vigueur, il s'imposait de prendre des mesures afin de préserver la viabilité économique de la production issue des vignes de ces zones. La seule solution, qui respectait le droit fédéral, consistait à faire bénéficier le vin en question d'une AOC. B. Agissant par la voie du recours en matière de droit public, B._ et C._, E._ et F._, G._, H._, I._, J._ et K._ ainsi que les sociétés A._ SA et D._ SA, demandent au Tribunal fédéral, sous suite de frais et dépens, d'annuler le règlement du Conseil d'Etat du 8 juin 2008. Ils concluent également à ce que le Tribunal fédéral dise, "qu'avec effet dès le 1er janvier 2008, le vin issu de vignes sises dans les zones franches de la Haute-Savoie et du Pays de Gex ne peut porter une indication de provenance telle que "appellation d'origine contrôlée Genève", "appellation d'origine contrôlée (suit le nom d'une commune genevoise)", "appellation d'origine Genève", "vin de Genève" ou toute autre indication donnant à penser aux consommateurs qu'il est issu de vignes sises dans le canton de Genève". Les recourants font valoir que le règlement attaqué viole le droit fédéral, en particulier les art. 63 de la loi fédérale du 29 avril 1998 sur l'agriculture (LAgr; RS 910.1) et 21 de l'ordonnance du 14 novembre 2007 sur la viticulture et l'importation de vin (ordonnance sur le vin; RS 916.140), ainsi que le droit international, à savoir l'Accord conclu le 21 juin 1999 entre la Confédération suisse et la Communauté européenne relatif aux échanges de produits agricoles (ci-après: l'Accord bilatéral; RS 0.916.026.81), plus précisément les art. 5 et 6 de l'Annexe 7 dudit Accord. Le Conseil d'Etat conclut, sous suite de frais et dépens, à l'irrecevabilité du recours et, subsidiairement, à son rejet. Les parties ont maintenu leurs conclusions au terme d'un échange ultérieur d'écritures. Invité à se prononcer sur le recours, l'Office fédéral de l'agriculture (ci-après: l'Office fédéral) a indiqué qu'il approuvait et soutenait la démarche genevoise qui consiste à mettre en place une AOC transfrontalière et permet la continuité d'une pratique existant depuis plusieurs décennies. C. Par ordonnance du 4 septembre 2008, le Président de la IIe Cour de droit public a rejeté les requêtes d'effet suspensif et de mesures provisionnelles contenues dans le recours. 