For posterity I'm going to post my own solution to this problem. None of the answers above or on related StackOverflow questions helped; most referred to menu entries that didn't exist, and the ones I could try did nothing. I searched other sites as well; there were about 6 different answers repeated many times, and none helped.
Short answer: I blew away the Eclipse install and replaced it. Then it worked. For me at least it wasn't a project or configuration option (at least not one I could get to from the GUI); something in the Eclipse program folder had gotten tweaked and only a new install could repair the problem.
I'm doing Android development using the "ADT" (Android Developer Tools) build of Eclipse. I did something to the configuration that made it start giving the above error (actually two errors, for gcc and g++ both). And I tried plenty of potential solutions (in addition to my own searching for options that might help) with no success.
Thing is, I didn't NEED gcc or g++ in the path. I'm doing Android development, and while both are used in the build process, I'm not using Eclipse to do the builds; I use the Android build system. And the C/C++ Build/Discovery options didn't even give me an option for setting paths for gcc or g++. Other answers I found elsewhere referenced menu entries that don't exist, and most seemed to be about helping people to use the normal C/C++ build within Eclipse, which I didn't need to do.
So I used this opportunity to download the latest ADT package from Google, and then I ran the new one, importing the existing project into a new workspace (just in case the old workspace was corrupted or otherwise part of the problem). No more annoying gcc/g++ error.