you could 301 everything to the closest similar product page/url instead of 404ing if these are entry pages that were ranking and getting traffic in search. by 404'ing them you'll lose those rankings, 301ing them will keep that ranking position but show the new URL in it's place.it all depend on if they were getting landing page traffic or not. also if any links are pointing to those pages and if they have any PR i would 301 them all instead of throwing the page juice away.
what could you be forgetting?
update sitemap.xml files and take the old ones off of the server and resubmit in Google
internal linking is all updated, sometimes people have blogs pointing to old URLs, if you're 404'ing then you need to update them, if you're 301'ing they can be left the way they are if it will be time consuming
make sure your robots.txt is updated, and people a lot of times put their sitemap.xml paths in the robots.txt so that would need to be updated
run a broken link checker on the site once done