I'm having the same problem. I changed my password yesterday (I Heartbleed the Internet!), but that might be a coincidence. None of my devices (iPad, MacBook, iPhone) can send emails from anywhere other than my home wifi. I have AT&T, but that doesn't explain why the MacBook and iPad can't send email on the work wifi. I get the p04 outgoing server error.
I deleted iCloud email from the phone and reinstalled it, but that didn't work. I tried to create alternate outgoing mail servers, but that isn't working (and they disappear).
I'm not sure when it started, since I was emailing just fine from home in SF this morning and noticed it wasn't working when I started emailing from my devices at work.
My workaround is to use a gmail account as my outgoing mail account for the time being.