Having experienced the same thing here at my job when we switched from one ecommerce platform to Zen Cart, here's a tip and an afterthought:
Write a 404 Redirect
This AUTOMATICALLY redirects search engines, as well as customers from a broken page to somewhere else so they don't see a "404" error, or better said, so they never land on a "404 Error" page at all! Do you have an .htaccess file in your store's root folder? Add this line to your .htaccess file:
ErrorDocument 404 /index.php
This means any 404 error will automatically redirect to your homepage.
But what if you want a custom 404 Error page with your logo? You could write your own page, call it "404.html" or "404.php" and place it in your shopping cart's root folder and add this line to your .htaccess file:
ErrorDocument 404 /404.php
Although one could argue whether it was right or not to do it that way, we opted for our own custom redirect page that made the customer feel everything was just fine and that they were still "in our website" and there wasn't some secret internet glitch that would cause them to lose confidence. So, we said "Oops" with our own logo and added a timer to automatically redirect them to the homepage after 5 seconds. The whole concept of a redirect really helps because it means their internet journey won't end on a broken page.
Now — I'm not an expert, but it's worth it to say that this might not work on some server types, but most servers are Apache/Linux, so I'm wagering you're in the majority and this would work for you.
AFTERTHOUGHT
In my experience, I have dealt with all kinds of clients, sites, both standard and ecommerce, and my clients have asked the same questions about making such major changes and how the search engines have 'lost' them in the mix. But that's always temporary. If you're the one who's neck is on the line for results, you just have to be honest and confident about the facts.
If you build the store, do it right, and drive the traffic there, the search engines will pick it up in time. I can say that I managed to get my company to get away form Joomla and switch to Zen Cart. For a few months, our links were bad on the search engines. However, I can honestly say that a year later, our sales are up 1000%~1500% - no kidding. The search engines have caught up with us and our target keywords have moved us up higher on the search results.
My point is — you should make your site, do it right, drive traffic there (sales, email blasts, etc.) and wait patiently for the search engines to catch up with you. Your situation is not unique and it can feel frustrating, but the power of Zen Cart and doing your site right has enormous benefits and the search engines will reward you kindly!
////// **LeatherJacketMedia.com**
"I'm no Zen Cart expert, but I did sleep at a Holiday Inn Express last night."