for years now, whenever I change my site around alot, like a big redesign or something, I make sure my htaccess has a 404 redirect in to send it to my index page, so that I don't lose any potential visitors I sure hope google wouldn't be so cruel as to punish my site because of that here is what I put in my htaccess: ErrorDocument 404 http://mydomainname.com/ that way any old pages that were indexed will at least be sent to the main page so that the visitor can find where they want to go from my main page
i will say if u use 404 widget which is offered in google webmaster tools it will help u , and im sure u will not lose ur visitors if use it. Good Luck