A mí me pasó lo mismo.
Lo que yo hice fue "liquidar" todos los contactos con alguna aplicación dedicada a tal fin y luego volver a importar desde la SIM y a correr.
De vez en cuando copio los contactos nuevos con otra aplicación a la SIM y listo.
Es un poco tostón pero estas cosas modernas son así. Antes elegías "contactos SIM", "contactos teléfono" y punto.