SSL support in evolution appears to require that the server also be running the obsolete smtps (TCP port 465) service -- it can't just negotiate STARTTLS over TCP port 25 as is now the standard (RFC 2487). Not sure if this is a bug, a feature request, or something I've misconfigured on my end ;-). My guess is that it's a feature request....
STARTTLS is on the feature list for the next version of evolution unless I'm completely misremembering things