Faits: A. Le 29 juin 2005, le Conseil d'Etat du canton du Valais a adopté le règlement concernant le statut du personnel de la haute école pédagogique (ci-après: RpersHEP/VS ou encore le règlement sur le statut du personnel HEP; RSVS 419.103) en application de la loi valaisanne du 4 octobre 1996 concernant la haute école pédagogique (LHEP/VS ou encore loi sur la haute école pédagogique; RSVS 419.1) et de son ordonnance du 12 janvier 2000 concernant le statut du personnel de la haute école pédagogique (OpersHEP/VS ou encore ordonnance sur le statut du personnel HEP; RSVS 419.102), publié dans le Bulletin officiel du canton du Valais du 15 juillet 2005 (BO/VS 2005, n° 28, p. 1584 s.) pour entrer en vigueur le 1er septembre 2005. Ce règlement comprend notamment les dispositions suivantes: art. 4 traitement de professeur - traitement de chargé d'enseignement 1Le traitement servi aux enseignants de la HEP est fonction du temps et de la nature des tâches attribuées en qualité de professeur et de chargé d'enseignement. 2L'enseignant de la HEP reçoit un traitement de professeur uniquement pour la part de son activité consacrée aux tâches de recherche et développement en science de l'éducation, aux prestations à des tiers et, le cas échéant, à la conduite de dossiers de formation des praticiens-formateurs, de gestion des stages des étudiants, de gestion des examens finaux, de coordination des enseignements, de gestion des formations complémentaires, de responsabilité du système de qualité. La part d'activité affectée à ces tâches doit représenter au moins 10 pour cent du temps de travail. 3En plus des exigences arrêtées à l'alinéa précédent, l'intéressé doit remplir les conditions suivantes: a) il doit être nommé pour au moins 50 pour cent d'un temps de travail annuel b) il doit assumer pour au moins 8 pour cent de son temps de travail les tâches courantes d'enseignement. 4L'enseignant qui ne remplit pas les conditions fixées aux alinéas 2 et 3 reçoit un traitement de chargé d'enseignement. B. Répondant à une mise au concours de "professeurs à la Haute école pédagogique du Valais (HEP-VS)" du 22 septembre 2000, A._, B._, C._, D._, E._ et F._ ont été nommés à titre provisoire au début de l'année 2001 en qualité de professeur à la Haute école pédagogique par le Conseil d'Etat du canton du Valais. Ils sont encore en fonction pour la période 2005/2006. Par courrier du 5 juillet 2005, ils ont reçu du directeur de la HEP-VS le règlement du personnel HEP. C. Agissant par la voie d'un recours de droit public déposé le 5 septembre 2005, A._, B._, C._, D._, E._ et F._ demandent au Tribunal fédéral, sous suite de frais et dépens, d'annuler le règlement sur le statut du personnel de la Haute école pédagogique du 29 juin 2005, plus particulièrement son art. 4. Ils invoquent la violation des art. 9 et 36 al. 2 et 3 Cst. ainsi que 57 Cst./VS. Le Conseil d'Etat valaisan conclut au rejet du recours. Lors d'un second échange d'écritures, les parties ont confirmé leurs conclusions respectives. D. Par ordonnance du 13 avril 2005, le Président de la IIe Cour de droit public a rejeté la demande d'effet suspensif déposée par A._, B._, C._, D._, E._ et F._.