OK, is it safe for me to assume that you are using the Maintenance Plan Wizards and you have a connection from the actual Maintenance task ---> the Notify Operator task?

If this is the case, can you confirm that in the Precedence Constraint Editor, that you have the Evaluation Operation set to "Constraint", Value set to "Failure", and "Logical And. A;; constraints must evaluate to True" checked?

Or is this a custom maintenance plan? If so, please provide the actual TSQL code you are using to generate the email on failure