Puede estar pasando que no todos tus contactos estén en la sim.
Has probado la sim en otro móvil a ver si aparecen todos los contactos? No estarán los contactos en la memoria interna de tu móvil anterior?
Esto casi seguro no es, pero a las sim se les llena la memoria con muchos contactos y después ya no pueden almacenar (más de 1000 contactos talvez), también puede haberse dañado.
Si es problema de software, al actualizar firmware o cambiar de rom el problema debe desaparecer, sino es problema de hardware y puedes hacer valer tu garantía.