Коллективный разум обнаружил в настройках ядра Линукса (как минимум Ubuntu Intrepid и Debian Lenny) параметры, которые мешали хорошему многопоточному декодированию H.264
Я попробовал, и стало заметно лучше
Сохраним на память:

for i in /proc/sys/kernel/sched_domain/*; \ 
  do echo $(( `cat "$i/domain0/flags"` | 16 )) \ 
  > "$i/domain0/flags"; done