Problème après reformatage complet du site

A cause d'un problème d'optimisation de base de donnée, celle-ci n'avait pas tenu le coup face au grand nombre de wallpapers (mon site en www). J'ai donc du rebuild mon site web avec une version plus stable. Malheureusement Google avait déjà indexé 450 pages, et du coups maintenant que je lui présente le nouveau sitemap il garde tout de même en tête les anciennes url.
Y'a-t-il un moyen de désindexer les anciennes url? Me faut-il juste attendre que google fasse le ménage?
Merci de votre aide.

 

J'ai cette erreur sur mon sitemap, et dans quasiment toutes les catégories:



Voila mon sitemap:
http://www.wallpapers-hd.com/sitemap

Vous n'auriez pas une idée de ce que ça veut dire et comment les réparer?

Merci d'avance

 

Bonsoir Benoit1
Merci pour ta réponse, mais quand je regarde l'erreur, je ne vois pas que ça redirige vers le sitemap
http://ece-bdx.com/ece/url.png

J'utilise un script php interne pour faire l'index ça m'évite de crawl tout le site et ça reste à jour plus facilement (2mn pour faire le sitemap contre 5h pour un outil classique) ça viendrait de là?

 

C'est le fait que ce soit formaté comme ça;
http://www.wallpapers-hd.com/sitemap/show_cat/9
Avec sitemap dans l'adresse qui pose problème donc? Qu'est-ce-qu'il faudrait à la place?
Merci de votre aide

 

Merci Je vais tacher de régler ce problème!