address completion in Evolution

Indeed. I'm experiencing the same problem, but I'm using GNOME evolution 2.22.3.1 (8.04).

What is the version of Evolution you're using?

I think this will work.
I have checked the "Personal"
item beside the "On this Computer" item.
However, it is not clear how to add to the adressbook
I see am item in the Message list
Add sender to Address book
which I suppose is necessary (in Thunderbird, the software automatically constructs
an addressbook from messages)
but it is not clear on how one can look and edit the Addressbook

Personal is your main address book, by default. You can make more address books, etc.

This will start indexing your "Personal" address book for auto completion. For example, you may want to setup a separate one for work and mark the "Personal" one as default on this P.C. It's entirely up to you.

Here's a quick reference about the address book:
http://library.gnome.org/users/evolution/stable/quickref-contact.html.en

Here's a more detailed reference about contacts:
http://library.gnome.org/users/evolution/stable/usage-contact.html.en

I think these are important to know.

Did you know you can sync your GMail Contacts & Calendar with Evolution? You sure can. Read how:
http://linux.com/feature/154875?theme=print

In my particular case, even after enabling auto-completion, it still doesn't work.

Are there addresses in your personal address book?

Can you please verify this since this is the address book you chose, via evolution, to use for auto-completion? Please make sure all options were chosen in your auto completion tab.

I can only have a Personal address book;
there are no other options available to me in the auto-completion tab
I am using Evolution 2.22.3.1 in Ubuntu 8.04