Add ubercart catalog paths to xml sitemap
Make sure that you have XML sitemap node enabled.

Go to /admin/structure/types and make sure that your product type in set for inclusion in the XML Sitemap by default. If you have to change it, then if the pages you already have are set to 'default' they will react properly. If they are set to 'exclude' you will have to edit each page and change it.

Then go to /admin/config/search/path/patterns and set your catalog path to catalog/[term:name]
and your catalog product page paths to catalog/[term:name]/[node:title].

If you have to regenerate your aliases, make sure that you retain the old alias, or use the Redirect to issue a 301 redirect for old aliases.

Then regenerate the site map. These steps should cover off any reason why the paths are not in your current sitemap.