TheMadScientist - 2:15 pm on Nov 11, 2012 (gmt 0) [edited by: TheMadScientist at 2:35 pm (utc) on Nov 11, 2012]
After thinking for a bit ... If it's the situation I described where the page receiving the redirect has changed over time, I think the best answer is to ignore it, because you're not 'doing it wrong' the way you have it.
In fact, you'd be 'more wrong' to change it to either a 404 or 410 than you have it now.
The biggest reasons I'd leave it as (ignore the notice) is:
1.) By changing it to a 404 or 410 you definitely lose any inbound link weight, age, history, etc. to the original page you had, but the way you have it, now (or in the future) you may retain a bit.
2.) Google doesn't always 'get it right' the way they have things, and if they notice the pages on the receiving end of redirects are generating soft 404s over time when the receiving page is updated the way the original would have been, they will likely eventually make a change on their end, and by 'fixing' yours to a solution other than the one you have you would miss out on any future adjustments they make in the handling on their end.
Note for future readers since it seems some like to post the technical difference in status codes according to strict protocol but ignore the actual handling of the status codes by search engines, even though this is a Google SEO Forum, not a 'HTTP/1.1 Protocol Forum', and search engine handling of status codes differs from the letter of the code handling 'by the book' a bit:
A 301 and 302 are mainly a semantic difference these days, so which you use is not a 'huge gotta change it' deal if it happens to be a 302. Yes, a 301 is 'more correct', but a 302 will work 'essentially the same'.
A 404 and 410 are purely a semantic difference and Google will not 'like your site more' because you use a 410 or 'like your site less' because you use a 404.
The only difference I know of in handling by Google is they will stop requesting a 410 sooner than they will stop requesting a 404, so if you 'freak out' at 404 notices in your WMT account, use a 410 and they'll go away sooner ... Other than that, it really makes no difference in the overall scheme of rankings whether a page that's 'not there' generates a 404 or 410.
[edited by: TheMadScientist at 2:35 pm (utc) on Nov 11, 2012]