I have a site map with a load of url's on it - but the URLs are old ones and they have all been 301 redirected - should I redo the site map or should I leave it and add the new urls? I dont want the search engines to de index any pages.
It is acceptable for your sitemap to change as your website evolves. So by all means, remove the old urls and only keep current ones. That being said, I don't think it will really help you much at all other than helping discover issues via Google Webmaster Tools.
You need to recreate your sitemap again and submit to the webmastertools, beside that you also can submit your URL to search engine and hope Google will recrawl and reindex your site within the short time.
Google won't deindex any indexed pages unless you set them to noindex. Go ahead and update the sitemap with the new links and everything will be fine.
Sitemap always create in xml-sitemap and add to GWT. sitemap provide the all page link to search engine and then index by google. sitemap inform search engine about any update in site.