Google contacts can not sync (update | commit): Cannot authenticate user: Invalid query

I can not sync with my Google contacts. I added a new address book and selected Google. I added my credentials.
First it did not load any contact. But after a while it loaded a few (96) of several hundreds and prompted a new error message. Unfortunately only partially in English. Note that I have not changed anything between the two messages.

The first error message was: "Suche konnte nicht durchgeführt werden. Diese Abfrage konnte nicht erfolgreich ausgeführt werden. Authentication Required"
The second message was "Die Hintergrundkomponente für dieses Adressbuch konnte die Syntax dieser Abfrage nicht analysieren. Invalid query"

ProblemType: Bug
DistroRelease: Ubuntu 11.04
Package: evolution 2.32.2-0ubuntu7
ProcVersionSignature: Ubuntu 2.6.38-10.46-generic 2.6.38.7
Uname: Linux 2.6.38-10-generic x86_64
NonfreeKernelModules: wl
Architecture: amd64
Date: Sun Jul 17 21:32:59 2011
EcryptfsInUse: Yes
ExecutablePath: /usr/bin/evolution
InstallationMedia: Ubuntu 11.04 "Natty Narwhal" - Release amd64 (20110427.1)
ProcEnviron:
 SHELL=/bin/bash
 LANGUAGE=de_DE:en
 LANG=de_DE.UTF-8
SourcePackage: evolution
UpgradeStatus: No upgrade log present (probably fresh install)