Скачайте в Яндекс.Вебмастере все страницы, которые находятся в индексе, проверьте их на доступность (все ли они правильно редиректят). Если страниц много, можно воспользоваться краулерами типа Netpeak или Screaming Frog SEO Spider, они способны массово проверить доступность страниц по списку.
Так же советую создать карту сайта sitemap.xml с новыми ссылками и загрузить её в кабинет вебмастера в соответствующий раздел.