Contactos en Android: Límite de eliminación superado

Hace unos días borré todos mis contactos de Android (con la aplicación "Borrar contactos"). No es un error, realmente quiero borrarlos.

Desde ese día, Android siempre muestra una notificación "Sincronizar: Demasiados contactos borrados".
Cuando hago clic en él, aparece un menú:

`Delete limit exceeded
There are 3960 deleted items for contacts, account xxx.xxx@gmail.com. What would you like to do?

• Delete the items.
• Undo the deletes.
• Do nothing for now.`

Cuando hago clic en Delete the items El menú desaparece y no parece ocurrir nada. Los contactos desaparecen, pero la notificación sigue ahí. Lleva días así. ¿Qué puedo hacer?