Al tener el mismo contenido por duplicado, en las URL's antiguas y en las nuevas, lo que deberías hacer es la utilización del
rel="canonical", de esa forma harás que Google vea cuál es la información original dentro de tu sitio.
No obstante, para el problema que nos presentas, la decisión más acertada sería la utilización de
redireccionamientos 301 de las antiguas URL's a las nuevas, de esa forma en las SERPS Google cambiaría las viejas por las nuevas, y no te aparecerían los errores 404, y por ende, no perderías ninguna visita ni perderías tampoco el valor SEO que habían cogido tus secciones internas en cuanto a posicionamiento en Google.