До развала Союза у всех граждан было гражданство СССР, а не союзных республик. Так в паспортах и было написано "гражданин СССР". Поэтому Вы явно что-то не поняли в объяснениях. Возможно, после 1992 года отец этого мужчины что-то с документами и гражданством накосячил и с тех пор эта неопределенность тянулась. Поэтому и сделали запрос в Узбекистан. А дела с гражданством решаются только через суд. Так что все это рабочие моменты.