Ok, I think I have tracked down the problem to a change that happened in site.py.  In comparing against a build that worked fine for Python 2.6.5, I noticed that the Modules subdir (which contains the shared .so files) was present on the sys.path for Python 2.6 but not for 2.7.  Digging deeper let me to the site.py module.  In Python 2.7 the behavior was changed so that the Modules path element was removed from sys.path. 

This is probably best explained by the patch I applied to revert to 2.6.x behavior, which fixed the compile problem for me:

--- Python-2.7.1/Lib/site.py    2010-10-12 18:53:51.000000000 -0400
+++ Python-2.7.1/Lib/site.py.addbuilddir-revert 2011-04-16 23:03:47.000000000 -0400
@@ -122,7 +122,7 @@
     s = "build/lib.%s-%.3s" % (get_platform(), sys.version)
     if hasattr(sys, 'gettotalrefcount'):
         s += '-pydebug'
-    s = os.path.join(os.path.dirname(sys.path.pop()), s)
+    s = os.path.join(os.path.dirname(sys.path[-1]), s)
     sys.path.append(s)

Obviously I imagine there was a reason why this change was made, so the above patch is probably not an appropriate universal fix.  I don't know anything about the original reasoning, but this change does seem to work for me on CentOS 5.5 now.

Notably, the issue I'm describing doesn't appear to have anything to do with gcc.  (Incidentally, I'm using gcc-4.1.2-48.el5.)