g1smd - 9:16 pm on Oct 20, 2012 (gmt 0)
The "error message" appears when a large number of pages suddenly change status in a short time scale. As the change is what you intended, you can either ignore it or you change the 404 status to 410 for those URLs.
I often use a simple PHP script to detect when bots request old pages that now return 404 and update a database entry for the URL such that those URLs then return 410 Gone for all future requests.
When Google finds a URL that returns 404, they test it once or twice more in the next 24 to 48 hours then do not revisit it for weeks or months. You have to be very quick to change the status from 404 to 410 (or whatever it should be) in order for Google to see it.
I only ever return 410 for URLs that used to exist, i.e. URLs that have returned content with 200 OK status at some time in the past. If the requested URL has never existed, I leave it returning 404 status forever.