This doesn't work in Evolution 2.9.4. (feisty)
I have the plugin enabled and the Preferences -> Auto completion -> Automatic Contacts checked.
** Changed in: evolution (Ubuntu)
Status: Needs Info => Confirmed
--
Automatic contacts are just broken
https://launchpad.net/bugs/68642