setup.py
gets its info from your installation of Python, specifically the distutils package of the standard library, from which it imports at least some functionality.
distutils.ccompiler provides the abstract base class CCompiler
describing your C compiler. For gcc, the typical concrete class is in distutils.unixcompiler and I think that's where you should start checking for the Mac in particular.
If it can help you to see how things are in a perfectly working Mac OS X 10.5 with the next-but-latest XCode (I can't install the latest one as it's 10.6-only) I'll be glad to share info about my installation -- but I think it would be more helpful if you told us about what Mac OS X release, what XCode release, etc etc, you have installed!-)
It's also important to know whether you're using the system-provided Python, a macports one, one installed from python.org (and, which one;-), and so forth -- each may have its own installation problems of course, but they'll tend to be different from each other!-)