OK, this was confusing. I was getting repeatable five minute builds, i.e. "make clean; reboot; time make -j3" (more or less :-) was reliably showing five minutes wall clock time.
Then I did "make distclean; ./configure; make depend".
After that, I got repeatable nine minute builds, i.e. make clean; reboot; time make -j3 was showing nine minute wall clock time.
Turns out, the difference was... I had been building without optimization. So configuring with CFLAGS="-g -O0" is almost a 2x speedup!
This is with gcc-4.2.3.
Might be handy to know when doing regressions.