Creating good redirects for broken links

Hi, we changed the theme of our wordpress site a couple of month ago wich altered the permalink structure of some custom post types and tags previously used. At the time I didn’t pay too much attention to it but now I am seeing 1900+ crawl errors (not found) on Webmaster tools and I am wandering if this doesn’t affect the ranking/quality of the site (although I can’t seem to find any of these old links in search results).
Some of those ‘not found’ links have even become totally obsolete (like tags that are no longer used) and I wouldn’t even know where to redirect those.
I have been experimenting with some plugins but recently started having performance issues with excessive CPU usage on my server and deactivated them again.
Is there some straight forward way of avoiding having all these ‘Not found’ errors on webmaster tools and does it even matter?

Thanks for your inputs!