Same happens with evolution-exchange 2.8.1-0ubuntu1. This is happening about once a day for me. Other times the auto-complete works fine.
** Attachment added: "another bug buddy output" http://librarian.launchpad.net/4941822/evolution-exchange-address-autocomplete-bugreport.txt -- Crashed whilst typing new recipient https://launchpad.net/bugs/61857 -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs