gcc-4.5.0とgcc-4.3.4で比較してみました。今度はどちらもccacheは通していません。
上がgcc-4.5.0で下がgcc-4.3.4です。

$ time make -j3 >/dev/null 2>&1
make -j3 > /dev/null 2>&1 1611.79s user 71.32s system 132% cpu 21:07.66 total

$ time make -j3 >/dev/null 2>&1
make -j3 > /dev/null 2>&1 753.78s user 68.05s system 169% cpu 8:03.95 total

4.5.0は4.3.4の倍以上かかってます。gccのバグでしょうかね？
Phoronixのベンチマークでは4.5.0で大幅なコンパイル時間の増加はなかったようなので、ちょっと変だと思い報告させて頂きました。