This problem is a real pain to deal with. It doesn't work very well.
This is applicable to Eclipse 3.4.1 / CDT 5.0.1
From what I can tell, when you create a "C/C++ Project" within CDT, it will try to auto-detect your include paths. Great idea, but the implementation is horrid.
If you delete or rename a directory, the old directory is leftover. If you rename the project, the old directory is leftover. When Eclipse can't find that old directory, it gives you that warning.
My solution is turning the automated discovery off entirely and managing my include paths manually. You need this list of include paths for things like ctrl-click (auto-navigate to defines/functions/files/etc) and shading out #define blocks. It builds the index off this list.
Here's what you need to do:
Right click on your project in the project explorer and go to properties.
Go to C/C++ Build -> Discovery Options
Uncheck "Automate discovery of paths and symbols"
Now go to C/C++ General -> Paths and Symbols
You'll see under the Includes tab Assembly, C and C++ languages with corresponding auto-discovered include directories.
Go to all 3 languages and delete everything.
Open your makefile and transcribe your includes into the corresponding language.
A project rename will still cause the indexer to break. ${project_name} and other globals do not seem to work. If you're having trouble, use the "Workspace" button to browse to the directory you want to include, as that seems to always work but entering it manually does NOT.
Hit apply, then OK.
Right click your project, go to index->rebuild
Restart eclipse.
This should fix things forever. Any time something improperly is shaded out due to a #define or #ifdef block, it's because that list of files is outdated. You'll also know that list is outdated if you get "unresolved inclusions" on #include lines.
Doug Schaefer, hopefully Google indexes this, you find your name, and you fix this awful implementation. =)