Andy_Langton - 11:05 am on Apr 8, 2012 (gmt 0)
As a quick addition to this thread, I managed to fix the problem in two instances. I doubt these are typical, but might make reasonable examples for some trying to troubleshoot:
In one case, the problem was with CTR for a particular URL. This was diagnosed by a check on rankings vs traffic (you can use Webmaster Tools for a basic idea of this, although the data is far too limited really). The cause was an issue with snippets which was decreasing CTR. Near instant recovery once the snippet was fixed.
In the second instance, there was a decrease in rankings across a number of pages. This was a DNS problem - the site in question redirects to drop the www subdomain. The www DNS record was faulty, which meant the site looked like it had lost thousands of links. This recovery is ongoing!
Hope this might give someone some new ideas on places to check when you get this rather vague message in GWT :)