Some more information:

Bob Arendt and I have been playing with the Fedora Core .spec file
for python on Fedora Core 15: 
the compile options we found seem to automatically (as we did non invoke
this option) invoke '-fno-builtin-memcmp' somehow?  We disassembled the
Python binary we built for the machine ourselves (via the spec file)
code and saw, yes, it was calling memcmp on the system, even though we
didn't bypass it explicitly.

Our conjecture is that the -m32 or -mtune=atom automatically turns the builtin memcmp off, but we're not sure (we're still playing with it). 

However, perhaps Fedora builds on a more generic machine: that generic build keeps the 'rep cmbsb'?

Frustrating.