Мне 20 лет, пошла менять паспорт. Отказали принять документы, т. к я родилась в Германии.

Да все просто.
Вы постарайтесь не упираться в абсурдность тех или иных действий, а понять их причины и естественность, и Вам станет намного легче управлять ситуацией.
Читаем Адм. регламент выдачи и замены паспортов

У Вас услуга - "замена паспорта" (есть еще услуга "получение паспорта")
Перечень документов, которые Вы должны предоставить для замены паспорта, указан в п. 35

Если Вы все подали, уполномоченное лицо обязано принять документы. В противном случае отказ ведет к тому, что Вы проживаете по паспорту, подлежащему замене, его в ФМС считают недействительным, т. е. налицо административное правонарушение ч. 2 ст. 19.15 КоАП РФ со стороны отказавшего лица.

Документы должны принять и уже далее проверить законность приобретения гражданства.
И при выявлении незаконности - отказать в замене паспорта
23. Основанием для отказа в выдаче паспорта является:
отсутствие у лица гражданства Российской Федерации;
недостижение гражданином возраста 14 лет;
непредставление документов, указанных в пунктах 35, 36 Административного регламента за исключением документов, необходимых для проставления обязательных отметок в паспорте (военный билет, свидетельства о рождении детей в возрасте до 14 лет, документы, подтверждающие регистрацию по месту жительства, свидетельство о регистрации брака, свидетельство о расторжении брака) ;
несоответствие размера и количества личных фотографий требованиям, предусмотренным подпунктом 35.3 Административного регламента;
отсутствие квитанции, подтверждающей уплату государственной пошлины.

Просто в данном случае должностное лицо побежало впереди лошади - оно стало полагать, что Вами не выполнено требование постоянного проживания на территории РФ на 6 февраля 1992 г. (см. указ Президента, настоящего мужика, которого мы все любим до одури) . При получении паспорта, да, требуется предоставить
34.4. Документы, свидетельствующие о принадлежности к гражданству Российской Федерации (при наличии обстоятельств, предусмотренных пунктом 51 Положения о порядке рассмотрения вопросов гражданства Российской Федерации, утвержденного Указом Президента Российской Федерации от 14 ноября 2002 г. N 1325).

Но при замене паспорта это не требуется, предоставляется сам паспорт гражданина РФ. А законность обретения гражданства пусть проверяют сотрудники ФМС. Изза лени они склонны возлагать на граждан свои обязанности, что также основание для обжалования их действий в прокуратуру по 25й главе ГПК РФ (помимо заявления о возбуждении дела по ч. 2 ст. 19.15 КоАП РФ) .

Для Вас тоже есть задача - прочесть законы о гражданстве РФ (их два) и Указ Президента и определиться, на основании какого пункта Вы приобрели гражданство РФ. Чтобы быть более подготовленной к разборкам.

Паспорт это доказательство.
Пишите жалобу в прокуратуру и вышестоящему начальству, требуйте привлечь болвана к ответственности по ст. 19.1 КОАП РФ - самоуправство.

Обратитесь в вышестоящую организацию ГУФМС.

У вас должен быть вкладыш о том, что вы являетесь гражданином России, его приклеивают в свидетельство о рождении

оформляйте двойное гражданство

Странно. А паспорт, который вы меняете, где вы его получали?

пусть созваниваются с немецкой стороной, и говорят, мол так и так, берите её себе! Вы не проиграете ;)

в росси, да и во многих странах мира любят деньги, так что предлогайте им не стесняясь

Им надо дать деньги на лапу, чтобы мозг не парили, у меня с паспортом та же фигня была