Generate a mail log file analysis from the e-smtih manager to show reasons for failure. It should give a clue to what is happening.
Depending on your situation, you may need to specify an smtp server for outgoing mail under Configuration...Other email settings in the manager.
Cheers,
Andrew