For simple Zend_Form_Element_Text override you can just do this:
$e = new Zend_Form_Element_Text('text_element');
$e->setRequired(true) // needs to be true
->addValidators(array('NotEmpty')); // needs to be explicitly set
$e->getValidator('NotEmpty')
->setMessage(
'This is my new message that you entered an empty string!',
Zend_Validate_NotEmpty::IS_EMPTY
);
For Multi elements though, you need to set the NotEmpty's breakChainOnFailure to true as below:
$e = new Zend_Form_Element_MultiCheckbox('text_element');
$e->setRequired(true); // needs to be true
->addValidators(array(
array('NotEmpty', true) // notice "true" is set for breakChain option
));
$e->getValidator('NotEmpty')
->setMessage(
'This is my new message that you entered an empty string!',
Zend_Validate_NotEmpty::IS_EMPTY
);