Me parece raro que ASP.NET no venga con validadores para los controles CheckBox y CheckBoxList.

De cualquier forma, Scott Mitchell escribió unos validadores que funcionan muy bien, de hecho funcionan sin necesidad de hacer PostBack.

Es cuestión de descargar los DLLs, ponerlos en tu fólder bin, registrar el Assembly en tu página y utilizarlos.

Toda la explicación junto con los archivos los puedes descargar de este post de 4GuysFromRolla.

OJO:
No funcionan dentro de un UpdatePanel de Ajax.