I forgot to mention that the setup in Evolution seems to go OK, but it doesn't seem happy with my user password. Oh, and I just realized that the time stamp on that message is VERY old, so that probably isn't the problem. I have tried both no encryption and TTS encryption and it seems to both fail with the same symptoms.
And a follow up question: Is TTS turned on for SMTP by default, and if so how do I turn it on? The documentation says there is a setting but I can't find it anywhere.