Yo hará un mes que cambié de sim porque la vieja no era 4G y también tenía los contactos guardados en la tarjeta. Un día me desaparecieron unos 90. Sospeché de la tarjeta, pero no por defectuosa, sino porque cada vez que introducía un acento en el contacto (no recuerdo si con la ñ me pasaba también) no me dejaba guardarlo por ser demasiado largo (y también me sucedía lo mismo en otro móvil con Lollipop) así que algo sospechoso debe haber. Tendría que probar en kitkat, a ver si Android tiene parte de culpa.
Como tenía un archivo vcf los pude recuperar (y cuando los importé los nombres con acento se truncaron todos a partir de la vocal acentuada). Ahora los tengo en el teléfono y de momento no ha pasado nada raro.