I am in the UK and eventually found the problem was due to my BT Home Hub Router. Not sure where you live, but of you are in the UK, this might work for you.
I found this fix below on https://discussions.apple.com/thread/4604180?start=15&tstart=0
It worked for me. If you can't link to the URL, here is the body of the text
There's an issue related to the BT homehub that is providing a hostname that is "syntactically incorrect" for several smtp server.
Here's how you can fix it.
Using your internet browser, go to the address "192.168.1.254
- Follow instructions to reset your password if asked.
- Then go to "Settings", then "Advanced Settings" and "home network"
You will see there all the devices that are connected or that has been connected before. It's gonna be easyer if yout computer is the only one connected.
Your computer should have a name like "unknown-xx:xx:xx:xx:xx ...
Click on this name, chose another name without any special characters, like "macbook" for exemple.
And then click on "apply"
- restart your computer.
That should fix the issue.
Credit goes to vincentfromcork for providing me with the solution.
Spread the word