Hi,
I added gcc 4.2 from the openSUSE 10.1 repository so I now have both
the 4.1.2 and 4.2.1 compilers installed. But still have glibc-2.4-31.1
installed. I see your result with 4.2.1 but not with 4.1.2 so I think
that there could be a difference in the compiler flags. I don't know
enough about those to help but I can test any suggestions.

$ gcc --version
gcc (GCC) 4.1.2 20070115 (prerelease) (SUSE Linux)
$ gcc -O3 sort-string-bench.c -o sort412
$ ./sort412

Benchmark with 1000000 strings of size 15

C qsort with C style compare: 0.630000

C qsort with Python style compare: 0.640000
NumPy newqsort: 0.360000

$ gcc-4.2 --version
gcc-4.2 (GCC) 4.2.1 (SUSE Linux)
$ gcc-4.2 -O3 sort-string-bench.c -o sort421
$ ./sort421

Benchmark with 1000000 strings of size 15

C qsort with C style compare: 0.620000
C qsort with Python style compare: 0.610000
NumPy newqsort: 0.550000

This is  the same as:
$ gcc-4.2 -O2 -finline-functions sort-string-bench.c -o sort421
$ ./sort421

Benchmark with 1000000 strings of size 15

C qsort with C style compare: 0.710000
C qsort with Python style compare: 0.700000
NumPy newqsort: 0.550000

(NumPy newqsort with -O2 alone is 0.60000)

For completeness, 4.1.2 using '-O2' versus '-O2 -finline-functions' is
NumPy newqsort: 0.620000 vs NumPy newqsort: 0.500000