Do you have this at the top of your robots.txt?
User-agent: *
Allow: /
Sitemap:
http://www.your.com/sitemapindex.xml
Do you have SitemapXML (formerly "Google Sitemap") installed, if so have you updated your map. In admin/configuration/Sitemap XML under Use Existing Files have you set that to false so it will update your map each time you add products? This would be the only thing that would cause that. Once Simple Seo is installed Google will start deleting the old urls you had before you installed seo.
Bookmarks