I upgraded to Edgy to find this still a bug. I took another shot by deleting my ~/.evolution folder and starting again with the setup. It worked. I'm happily using an exchange server with evolution. -- evolution-exchange: unable to setup exchange account https://launchpad.net/bugs/25106