Yo tengo exactamente el mismo problema. Cuando pongo una o dos letras en la búsqueda, se queda pillado y pasados unos segundos aparecen los contactos. He borrado datos de contactos y buscado permisos de otras aplicaciones y nada igual. Y como dices me pasa desde esta última actualización.