Faits: A. X._ est un commerçant itinérant, établi à Y._, dans le canton de Fribourg. Il déclare avoir participé durant quinze ans à l'Abbaye de Fleurier pour y vendre ses produits (caramels à la crème, amandes grillées, bibers, biberlis, pains aux poires, crêpes, gaufres, hot-dogs, sandwichs, sucettes, pop-corn, barbes à papa et nougats). Sa participation a été remise en cause en 2004; dans un premier temps, le Conseil communal de Fleurier (ci-après: le Conseil communal) a refusé de lui octroyer un emplacement puis, le 24 juin 2004, il lui a accordé une place à certaines conditions; toutefois, cette décision serait intervenue si tard que l'intéressé n'aurait pas pu en faire usage. X._ est cependant resté en contact avec le Conseil communal; il a présenté, le 16 novembre 2004, une demande de place pour l'Abbaye de Fleurier de 2005; il a encore écrit au Conseil communal le 8 décembre 2004, en se référant notamment à son inscription à l'Abbaye de Fleurier de 2005 et en évoquant la possibilité d'une procédure judiciaire. B. Le 14 décembre 2004, le Conseil général de Fleurier a adopté le règlement de l'Abbaye de la commune de Fleurier (ci-après: le Règlement). Le Conseil d'Etat du canton de Neuchâtel (ci-après: le Conseil d'Etat) a approuvé le Règlement par un arrêté du 25 janvier 2005 (ci-après: l'Arrêté). L'Abbaye de Fleurier est une foire organisée une fois par année, le week-end précédant la fin de l'année scolaire (du samedi à 14h00 au mardi à 02h00); elle a lieu à la place de Longereuse et à la rue de la Place d'Armes. L'art. 2 du Règlement, ayant pour note marginale "Ordre de Réservation", dispose: "1 Les emplacements pour les marchés forains (carrousels) sont attribués sur la base de contrats spécifiques signés d'une part par les forains et d'autre part par le Conseil communal. 2 L'attribution des places pour les stands et guinguettes se fait dans l'ordre suivant: - les sociétés et marchands du village, - du district du Val-de-Travers, - du canton de Neuchâtel, - de Suisse romande, - les marchands des autres cantons suisses, pour autant qu'il y ait encore de la place. 3 L'attribution des places pour les stands et guinguettes n'est pas un droit acquis. La demande doit se faire chaque année." Le 2 février 2005, le Conseil communal a répondu à la lettre de X._ du 8 décembre 2004, en disant que son inscription serait examinée au regard de la nouvelle réglementation communale, et il lui a envoyé une copie du Règlement ainsi que de l'Arrêté. C. Agissant par la voie du recours de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'Arrêté et le Règlement. Il fait essentiellement valoir que l'art. 2 al. 2 du Règlement viole la liberté économique (cf. art. 27 Cst.), l'égalité de traitement (cf. art. 8 Cst.) et la primauté du droit fédéral (cf. art. 49 Cst.) dans la mesure où il enfreint la loi fédérale du 6 octobre 1995 sur le marché intérieur (LMI; RS 943.02), en particulier l'art. 3 LMI. Il allègue aussi l'absence de voie de recours dans le Règlement. La commune de Fleurier et le Conseil d'Etat concluent, sous suite de frais, principalement, à l'irrecevabilité du recours et, subsidiairement, à son rejet. La commune de Fleurier conclut en outre à l'allocation de dépens. Un deuxième échange d'écritures ayant été ordonné, le recourant et la commune de Fleurier ont confirmé leurs conclusions, alors que le Conseil d'Etat a renoncé à s'exprimer.