I had the exact same problem that you described, and I fixed it by telling Mail to use pot 587 instead of port 25.
My ISP, SBC/AT&T, states on their website that they block port 25 to prevent spam (that's like hitting a nail with a thermo-nuclear weapon), and that you can try using port 587 instead.
So, I tried port 587 for smtp.mac.com and it worked! I hope this helps!

Thanks for the post, but you realize this thread is 3 year old, right? :)

Off topic, I wonder how long before spammers and zombifiers start spamming from port 587 too?