С чего нам начать процедуру установления отцовства?

Добрый день! Подскажите пожалуйста с чего начать чтобы доказать родство с умершим отцом. Причина в том что при рождении у него было имя Леонид. Когда паспорта менялся имя изменили на Алексей. Все дети которые были рождены носят отчество Алексеевич. После очередной смены паспорта обратно вписывают имя Леонид. Почему отец на месте не решил этот вопрос ни кто уже не узнает. Что теперь делать детям и с чего начать решать эту проблему?

Я родила дочь в турции. Получила на нее свидетельство о рождении с вкладышем отметкой о гражданстве в консульстве РФ. Далее на основании этого получили загранпаспорт и выехали из Турции. Далее в России мы получили снилс, инн и прописала по месту прописки родителя. В паспорт РФ я отметила отметку, что она моя дочь. Спустя 2 месяца мы выехали в Турцию на месяц-1,5. Там же в Турции я вышла замуж, по возврату я легализовала брак в России. Муж турок согласился стать отцом и мы по обоюдному согласию сделали установление отцовство. это произошло после 7 месяцев как дочь получила гражданство. Естественно свидетельство выдали новое, где заполнена графа отец, но при обращении в органы МВД по месту прописки нам отказали в проставлении штампа о гражданстве в свидетельстве Рождении. Сказали, что у Вас обстоятельства поменялись и гражданство утеряно. Вопрос как так? Как возможна утеря гражданства, если допустим появился отец иностранец. Как возможно, что она была гражданкой рф и резко стала лицом без гражданства? Получается у нас что гражданство меняется и присваивается по отцу?