Давольно исчерпывающе...
Если скажешь какой почтовый сервер (pop/imap, smtp) и какие параметры вводил (ну свое имя и пароль забей иксами), и какую ошибку выдает evolution при отправке, то, возможно помогу.
Там есть тонкости. Например при настройке smtp mail.ru (да и других) нужно в user name вводить не user, а user@mail.ru.