Littleone: Российское гражданство

У нас такой вопрос: пошли оформлять гражданство ребенку, потребовались архивные справки родителей о месте прописки в 1992 году. Папа на тот момент имел учебную прописку в СПб (родился он в Узбекистане, видимо, там и была постоянная прописка). Живет он в России с 1986 года, до 1993-го была эта самая учебная прописка, потом - по молодой безалаберности - до 96-го никакой, потом постоянная прописка в разных российских городах. В 2000-м он поменял паспорт СССР с вкладышем о гражданстве на российский (это было в Калининградской обл.). Видимо, на тот момент (или в том месте) никто не обратил внимания на то, что в 1992-м прописка была учебная, и без каких-либо проблем ему поменяли паспорт на российский. А сейчас в паспортном столе милиции нам сказали, что паспорт этот якобы недействителен, что выдан он "ошибочно", что гражданство определяется не паспортом, а какими-то милицеско-овировскими списками, и теперь нам необходимо проходить муторную процедуру получения гражданства, и т.п.
Что делать?

Операции над сообщением: