Что делать с запретом на въезд, выданным по ошибке?

гр.узбекистана проживающий в перми.уехал в москву в посольство узб. по причине потери паспорта.там выдали сертификат и 23 января на самолете улетел к себе на родину делать паспорт.28 февраля был сделан паспорт.спустя два дня гр.поехал обратно но на границе его не впустили сказали запрет у него и никаких документов при этом не дали.в перми через адвоката сделали запрос о причине запрета.т.к думали что со дня вьезда и выезда прошло чуть более 90 дней но он не виноват потерял документы и пока делался сертификат был превышен срок нахождения на несколько дней.и это причина запрета.а оказалось что в базе фмс по нынешний день он числится как вообще не выехавший из рф и естественно это уже большое нарушение и его по базе разыскивают как не оформлявшего документы.что теперь делать.как доказать что он выехал давно.ведь сейчас с таким случаем это серьезное нарушения и естественно запрет серьезный.три месяца как его в россии нет.