La solución más óptima, aunque bastante compleja sería hacer una 301 por cada URL antigua a la URL nueva, puedes crearte un pequeño script que acceda a la base de datos y lo haga.
Este enlace puede ayudarte a entender la redirección 301 (según Google)
http://googlewebmaster-es.blogspot.c...practicas.html