Cuando se cambia el nombre de una url es necesario hacer una redirección 301 para que Google sepa que la url ha cambiado de forma permanente.
Lo que ocurre es normal, Google debe encontrar las nuevas urls, pero la valoración de las antiguas la has perdido.
Si el cambio de nombre sigue algún patrón, podrías aprovecharlo para hacer la redirección usando el archivo .htaccess.
Cambio de URL redirección 301 con .htaccess
Sería aconsejable también que hiceras un sitemap. No necesitas pedir reconsideración, en cualquier caso la opción aparece una vez que estás registrado en las
herramientas para webmasters de Google.