Thanks for the bug report. I installed the attached patch into coreutils 
on Savannah. It builds on your idea with several other changes:

* There's a similar issue with cksum.c and pclmul.

* configure.ac can be simplified, since it seems there's no point 
compiling these instructions if __builtin_cpu_supports doesn't work.

* This lets us simplify the source code a bit more.

Please let me know if the attached patch works for you.

PS. Does the attached cksum.c / pclmul change fix any user-visible 
misbehavior? If so, what should we put into the NEWS file?