Las antiguas urls aún quedan accesibles?
Entonces programar un poquito y usar el
rel=canonical te puede salvar de esta situación, sería casi como un 301... solo que muchísimo más facil de implementar.
En cuanto al sitemap, borra es éste las urls antiguas y agrega las nuevas.
saludos!