С предоставленным Apple gcc 4.2 [gcc версия 4.2.1 (Apple Inc., сборка 5566)] на Leopard я получаю те же результаты, что и вы (за исключением того, что у моего MacBook меньше ядер).
In a serial region; max threads are : 2
In a parallel region; max threads are : 1
То же для 4.3.4 от MacPorts.
Однако с gcc 4.4.2 и 4.5.0 20091231 (экспериментальная) от MacPorts на том же компьютере я получаю:
In a serial region; max threads are : 2
In a parallel region; max threads are : 2
Похоже, что это не проблема Mac против Linux, но из-за версии gcc.
PS OpenMP может выполнять вложенный параллелизм.