Well if Xcode was able to build and run that template we know the Obj-C compiler is installed somewhere. It would appear that Xcode can find it, but gcc can't. That points to an installation problem. Did you have any other dev tools installed prior to installing Xcode 3.1.2? Installing over a previous version requires cleaning out as much of the old dev tools as you can. For that reason I don't want to ask you to re-install 3.1.2 unless it seems really necessary.
I don't know how gcc finds its components. We have 2 or 3 developers around here who would know (e.g. eric meyers), and I hope one of them will take a look at this thread. For now the only thing I can think to check is your Terminal PATH environment variable. This is mine:
PATH=/usr/bin:/bin:/usr/sbin:/sbin:/usr/local/bin:/usr/X11/bin:.
Type 'echo $PATH' or 'printenv' and see if your path is the same (ignore the colon-dot at the end; I put that there).
gcc might have a config file somewhere. I'll do a little research as soon as I can, but I'm hoping one of the guys I mentioned will stop by before that. Can you do your work from Xcode for awhile? The source editor is way cool. Just use the Foundation Tool template (File->New Project->Mac OS X->Command Line Utility->Foundation Tool).
