Tim,
You'd have better luck if you used the Nios II Software Build Tools (command line based). The Makefile structure is easier to follow and it gives you a reasonably complete "copy" of everything you need to build.
You'll find examples of this flow in the software_examples sub-directory of every single hardware example that's shipped with the software ($SOPC_BUILDER_KIT/examples/[verilog|vhdl]). EDIT: in the <board>/software_examples subdirectory.
Now, to your question/issue... I think you might be confusing GCC by specifying a bit too much. GCC has built-in paths that are searched. Type "nios2-elf-gcc -v -x c++ -E -" to get a list of which# include paths are automatically searched, among other things.
Cheers,
-slacker