Faits: A. Le 11 février 2005, la Commission Mesures structurelles du Grand Conseil du canton du Valais a présenté une motion visant à modifier la loi fixant le statut des fonctionnaires et employés de l'Etat du Valais (loi sur le statut des fonctionnaires, LSF; RS/VS 172.2), afin que les chefs de service soient engagés non plus comme fonctionnaires, mais par contrat de droit privé. Il s'agissait d'instituer une certaine souplesse dans l'organisation de l'administration et d'éviter notamment que "des structures ne perdurent qu'en raison d'un chef nommé dans un contexte révolu". Dans sa réponse à la motion, le Conseil d'Etat valaisan estima que les objectifs de souplesse pouvaient être atteints dans le cadre de la législation existante; les mesures de réorganisation ne concernaient pas que les chefs de service. La motion ayant été acceptée par le Grand Conseil valaisan le 13 mai 2005, le Conseil d'Etat a présenté un projet de loi visant à l'abolition du statut de fonctionnaire pour les chefs de service et à l'instauration de rapports de travail de droit public; cela permettait d'atteindre les buts visés par la motion et ne nécessitait pas, au contraire d'un engagement de droit privé, de changements d'ordre constitutionnel. B. Le 14 février 2008, le Grand Conseil du canton du Valais a adopté la modification de la LSF, portant sur la modification des articles 1 al. 2 et 2 al. 2 dont la nouvelle teneur est la suivante: Art. 1 Champ d'application 2Les dispositions de l'article 5 (durée de la période administrative), de l'article 6 (nomination et temps d'essai) ainsi que des articles 33 à 35 (résiliation et renouvellements des rapports de service) ne sont pas applicables aux chefs de service (rapport de droit public). Sont applicables à cet égard les dispositions du code des obligations en la matière. Art. 2 Définition de la qualité de fonctionnaire et d'employé 2Sont considérés comme employés, sous rapport de droit public, les chefs de service et la personne qui est nommée à titre d'essai. Ils ne disposent pas du statut de fonctionnaire. C. Gilles de Riedmatten ainsi que dix-neuf consorts, tous chefs de service au sein de l'administration cantonale valaisanne, forment un recours en matière de droit public. Ils concluent à l'annulation de la modification législative du 14 février 2008. Le Grand Conseil valaisan conclut au rejet du recours dans la mesure où il est recevable.