[Broquen]

Otra cosa que puedes probar es borrar los datos de la aplicación "contactos" o de la aplicación "teléfono" (aunque con esta última opción imagino que se perdería el registro de llamadas, pero no estoy seguro).