Did you configure an SMTP server with your mail account in evolution
or thunderbird ?

You need to tell your mail client what server will take care of
sending your mail.

In evolution, go Preference->edit your account-> "Send Mail" tab
and check if everything is set OK (including your User ID).

And try again!

If nothing works, the I would suspect a firewall or a proxy or
something like that. You should use wireshark to sniff the
conversation and find where exactly is the culprit.