I once had over 10,000 "not found" errors and around the same amount of "unreachable" in my webmasters account. Due to changing permalinks and some other stuff, and my site suffered a great deal on Google.
I have just checked again, I now only have 300 "not found" errors, and no unreachable errors. I didn't do anything in particular, I guess Google just updated itself and found my links again.
My site is now being indexed on Google again, and I'm getting good traffic.
So yeah, I think it's just a matter of waiting for Google to crawl your site again.
Well, at least that's all what I done.