был гр. КР когда получил гр. РФ и пошел менять военник альтернативной службы то ему отказали..

Что за глупости, если альтернативная служба в другом государстве приравнена к военной службе по ФЗ, тогда проблем быть не должно! Иди и получай военный билет в военкомате по месту постановки на воинский учет. Обязаны выдать.

Такой процедуры как обмен иностранного военного билета у нас вообще не существует. После принятия гражданства РФ вы в любом случае будете направлены на медицинское освидетельствование для определения категории годности, по результатам которого либо призывная комиссия будет рассматривать вопрос о призыве, если вы не достигли непризывного возраста 27 лет, либо после этого возраста решением военкома вы будете зачислены в запас. А иностранный военный билет с нотариально заверенным русским переводом понадобится военкомату только в одном случае, если вы в другом государстве прошли именно военную службу. В этом случае повторно призыву вы уже не подлежите.

А прохождение АГС в другом государстве за причину для освобождения от призыва согласно законов РФ не засчитывается.

В соответствии с ФЗ "О воинской обязанности и военной службе" в России освобождаются от призыва на военную службу лица ПРОШЕДШИЕ ВОЕННУЮ (!!) СЛУЖБУ В ДРУГОМ ГОСУДАРСТВЕ.. .

.. альтернативная служба в Киргизии (как и в РФ) - она НЕ военная, она ГРАЖДАНСКАЯ, поэтому при получении гражданства РФ такой гражданин будет призван на ВОЕННУЮ СЛУЖБУ... .
..когда отслужит, тогда и выдадут военный билет