De la forma que estás intentando validar, va a mostrate el mensaje "Es necesario que seleccione un servicio" cada vez que un item del checkboxlist no esté seleccionado, me parece que podrías hacerlo de la siguiente forma:
Código:
If cbAA.SelectedIndex <> -1 Then
Iblmessage.Text = "Es necesario que seleccione un servicio"
Else
Iblmessage.Text = ""
'....
End If
Deberías considerar también la validación en el lado del cliente y no hacer un postback sólo para indicar que el usuario no seleccionó un elemento del checkboxlist
Saludos