I started with trying Josh Kelleys and mmmmms answers without any luck, but I finally fixed it by checking my include paths.
One way to see them are in the Project Explorer, expand project and there should be an entry "Includes". Inside that, check for a small yellow warning triangle on each include path. If that triangle is present eclipse most likely doesn't recognize the path.
The include paths are edited through right-clicking on "Your project" in the Project explorer, then choose "Properties" --> C/C++ General --> Paths and Symbols --> Includes.
I see three language options, Assembly, Gnu C, Gnu C++. Choose the correct one before starting to add paths (likely Gnu C++). After adding all the paths, -->Apply --> Ok and rebuild index if you're asked to.
My erroneous workspace paths looked like MyProject/MyProject/folder when it was supposed to be MyProject/folder.
For me the "Problems"-view is always slow to update, even after rebuilding index. To be sure that the error is still there, double-click the problems entry so that eclipse opens/reloads the file in question. This often seems necessary for me to update the "Problems" view.
I don't really know if it was eclipse or my scm that messed it up. Anyway, hope it helps someone!
I use Luna and builds with an external makefile.