Notification mail not sent on failure
Open your job in the management studio and go to the backup step properties and check whether it looks like this



I suspect "On failure action" Is not setup properly.