Да, при условии, что для Valdiator включена проверка на стороне клиента. Существует клиентский API, к которому вы можете подключиться. Смотрите это:
http://msdn.microsoft.com/en-us/library/aa479045.aspx
Прокрутите вниз и прочитайте раздел «Спецэффекты», в котором в примере используется RegularExpressionValidator. Обратите внимание, что он меняет цвет фона, а не изменяет текст в метке, но главное - увидеть, где вы можете разместить свой собственный код. Также обратите внимание, что вы не можете изменить представление метки server . Все, что вы можете сделать, это обычные манипуляции с Javascript.