Thanks for the bug report. Unfortunately, I cannot reproduce the problem with coreutils 8.7, either on RHEL 5.5 x86-64 or on Ubuntu 10.10 x86.
Which version of coreutils are you running? And on what platform? How did you build it? Can you reproduce it with --parallel=2? If not, which value of --parallel is needed? If this is coreutils 8.7, can you get a core dump and a GDB backtrace?