It is absolutely impossible to set custom element validation message if Zend_Translator is applied to Zend_Form. Please see my example...

class App_Form extends Zend_Form 
{

    public function init()
    {

        parent::init();

        //creating and assigning simple translator
        $translations = array(
            Zend_Validate_NotEmpty::IS_EMPTY => 'Value is required for this field.' //just one line of translations as example
        );
        $adapter = new Zend_Translator('array', $translations);
        $this->setTranslator($adapter);

        //now we're going to add form text element
        $element = new Zend_Form_Element_Text('firstname');
        $element
            ->setRequired(true)
            ->setFilters(array('StringTrim'))
            ->addValidator('NotEmpty')
        ;

        //now we're overriding error message for key with name Zend_Validate_NotEmpty::IS_EMPTY
        $element->getValidator('NotEmpty')->setMessage('Please enter your first name.', Zend_Validate_NotEmpty::IS_EMPTY);
        $this->addElement($element);

        $this->isValid(array('firstname' => ''));
        print_r($this->getErrorMessages());
        //we'll still get "Value is required for this field." message
        //if we will try to disable translator we'll get correct message "Value is required for this field."

    }

}

This error occures when Zend_Form::getErrorMessages() method is called. This method overrides current message templates with translated message templates.

So, it seems impossible complete this task without modifying Zend_Validate_Abstract