Par conséquent, il y a lieu d'annuler la décision du Conseil d'Etat du 19 août 2009 et de lui renvoyer la cause pour qu'il en complète l'instruction sur la question du comportement des recourants en cours de procédure et leur donne l'occasion d'exercer leur droit d'être entendus, avant de rendre une nouvelle décision.
6. Vu le sort de la cause, il est statué sans frais, les autorités cantonales n'en payant pas (art.47 al.2 LPJA).
Par ces motifs,
la Cour de droit public
1. Admet le recours et annule la décision du Conseil d'Etat du 19 août 2009.
2. Renvoie la cause à l'intimé au sens des considérants.
3. Statue sans frais.
4. Ordonne le remboursement aux recourants de leur avance de frais.