Hace unos días abrí un post apuntando un problema similar, sin embargo, un usuario consiguió que me lo cerraran, instantes después, alegando que había infinidad de hilos hablando del mismo tema.
Lo cierto es que estos hilos hablaban de problemas de sincronización que no era a lo que me estaba refiriendo.
En cualquier caso, al final encontré la solución a los problemas relacionados con el listado de contactos que reportan muchos usuarios. Tambíen se solucionan los problemas de las aplicaciones que, como Whatsapp, cargan el listado.
Haz lo siguiente. Menú de ajustes - apps y busca la aplicación de contactos 'Contacs storage'. Pulsa en clear data. Asegúrate de tener los contactos en la tarjeta sim, o en cualquier otro sitio, para poder importarlos de nuevo.
Espero que esto solucione tu problema.