Возможно, что и так. Все зависит от того, как ты сделал синхронизацию. Если ты захватываешь мьютекс, защищающий все дерево всеми потоками на все время выполнения задачи, то не удивительно, что работает только один поток.

Если время работы программы заметное (несколько секунд и более) и показатель около 27% - то скорее всего  реально нет распараллеливания или оно, как отмечено bsa, вырождается из-за каких-то синхронизаций. 
В Windows в диспетчере задач во вкладке быстродействие можно видеть графически загрузку отдельных ядер.
(Можно также  попробовать сравнить тайминг с последовательным аналогом программы)

А вообще не исключено, что параллельное выполнение потоков (не привязанное явно к логическим процессорам, если таковое возможно), будучи вырожденным (благодаря неудачным синхронизациям) в последовательное, распределяется операционной системой  на одно ядро.

Это сообщение отредактировал(а) FCM - 12.11.2011, 10:39

mrgloom, не хочу гадать. код выкладывай.