There are several things you could check. First of all, what do the URLs in the sitemap look like? Do they have the new URL paths? If not, you might have to regenerate your sitemaps and check again.
Next up, check if the sitemap is imported correctly, which will probably be the case.
Apart from that, you should enable the canonical URLs, so search engines will only have one path to index, even when it's coming in from an incorrect path. You can check if the canonical URLs are enabled by opening a category or product page and check the meta tags. If there is no canonical there, you can easily enable it by going to System > Configuration > Catalog > Catalog and then look under the Search Engine Optimisations tab for the options Use Canonical Link Meta Tag For Categories and Use Canonical Link Meta Tag For Products. Make sure they're both set to "Yes". The canonical URLs make sure search engines will only index those URLs, no matter what the URL is it will use to show the page.
And last but not least, make sure you have redirects from the old URLs to the new URLs, so everyone (search engines and visitors) are redirected to the correct URL.