После проверки пришло предписание о недействительности диплома и необходимости нострификации

Полагаю, что требование о нострификации незаконно. Вам нужно получить письменное мотивированное требование рособрнадзора, для того, чтобы можно было его оценить на предмет законности. 

Вот есть их же разъяснительное письмо по этому вопросу. 

<Письмо> Рособрнадзора от 01.04.2014 N 01-52-574/06-1295

<По вопросу признания в Российской Федерации документов об образовании и (или) квалификации, выданных на территории Украины>

В соответствии с частями 2 и 3 Федерального закона в Российской Федерации признаются иностранное образование и (или) квалификация, подпадающие под действие международных договоров о взаимном признании, а также полученные в иностранных образовательных организациях, перечень которых устанавливается Правительством Российской Федерации (распоряжение Правительства Российской Федерации от 19.09.2013 N 1694-р).
Обладателям иностранного образования и (или) иностранной квалификации, признаваемых в Российской Федерации, предоставляются те же академические и (или) профессиональные права, что и обладателям соответствующих образования и (или) квалификации, полученных в Российской Федерации, если иное не установлено международными договорами о взаимном признании.
Между Российской Федерацией и Украиной действуют следующие международные договора о взаимном признании:
— Соглашение о сотрудничестве в области образования (Ташкент, 15 мая 1992 года);
— Соглашение о принципах признания и нострификации документов об ученых степенях, сопоставимости ученых степеней (Алматы, 17 мая 1993 года);
— Соглашение между Правительством Российской Федерации и Кабинетом Министров Украины о взаимном признании и эквивалентности документов об образовании и ученых званиях (Москва, 26 мая 2000 года);
— Соглашение между Правительством Российской Федерации и Кабинетом Министров Украины о сотрудничестве в области аттестации научных и научно-педагогических кадров высшей квалификации (Харьков, 21 июня 2002 года);
— Протокол между Правительством Российской Федерации и Кабинетом министров Украины о внесении изменений в Соглашение между Правительством Российской Федерации и Кабинетом министров Украины о взаимном признании и эквивалентности документов об образовании и ученых званиях от 26 мая 2000 года (Киев, 28 января 2003 года).
В указанных международных договорах предусмотрены поименованные документы об образовании и (или) квалификации, которые в соответствии с частью 3 статьи 107 Федерального закона взаимно признаются странами без процедуры признания образования и (или) квалификации, полученных в иностранном государстве (свидетельство о признании иностранного образования и (или) квалификации на территории Российской Федерации не предусмотрено) (далее — процедура признания).
Вместе с тем, согласно части 4 статьи 107 Федерального закона, документы об образовании и (или) квалификации, не попадающие под действия международных договоров требуют прохождения процедуры признания в соответствии с Административным регламентом предоставления Федеральной службой по надзору в сфере образования и науки государственной услуги по признанию образования и (или) квалификации, полученных в иностранном государстве, утвержденного постановлением Правительства Российской Федерации от 24.12.2013 N 1391.

А.Ю.БИСЕРОВ