Hola Naye!!
Puede ser que no se hayan borrado y que se hayan ocultado en el iPhone. Comprueba qué contactos tienes visibles en la app Contactos del iPhone, o la pestaña Contactos de la app Teléfono. Pulsa en Grupos, de arriba a la izquierda. Aparecerá una lista con los contactos de las diferentes cuentas que tengas configuradas en el iPhone. Asegúrate de que la opción "todos los de iCloud" esté activada.
Si la opción anterior ya estaba activada, entra en la web de iCloud.com y, en la zona de Ajustes, Recuperar contactos, comprueba si los contactos que han desaparecido están ahí.
Ya nos contarás que tal te ha ido.
Saludos!!