Next up, mail client configuration settings. (I wish I had seen that screenshot sooner, but that's okay.)
Have you tried any mail client other than Evolution, or tried from any location on the Internet other than your current location?
Many ISPs block outgoing traffic on port 25, so you'll never be able to send mail using that port. (The logic, while flawed, is that less SPAM will come from compromised PCs if they block port 25.)
Try using port 587 for your SMTP connection. (This is the same port you will use even with STARTTLS enabled.)
If you are using SSL for some reason (instead of STARTTLS), try port 465.