Google Search Console y errores 404

Hola betas
Una pregunta, estoy teniendo un grave problema de SEO. Veran tenía un dominio digamos MiDominio.com que funcionaba bien. Tuve un problema y decidí hacerle algunos cambios. Mis post ANTES eran publicados como MiDominio.com/PostDelDia pero modifiqué eso para que vaya antes la categoria principal.O sea ahora es MiDominio.com/Categoria/PostDelDia como consecuencia de esto Google marcó errores 404 y me rechazó más de 900 páginas según su Search Console. Ya he eliminado varios de esos errores PERO aun quedan como 200. Mi pregunta es ¿se solucionará eso? Es decir, Google medio que me ha penalizado.... ¿se levanará la penalidad? Hice ese cambio para mejorar el SEO, imagine que esto pasaría pero no que sería tan grave.
Había pensado también cambiar de Dominio. Pero no sé... espero sus consejos. Gracias.

Al hacer el cambio lo ideal era redireccionar las url antiguas a las nuevas para evitar problemas. Ahora lo mejor es redireccionar las url que aun te marcan error a las nuevas con categoria. Google vuelve a rastrear y todo arreglado