can't recall off the top of my head. normally i rebuild them only when creating a toolchain for building distros, not updating an existing one. having said that, i would still use the same order you are using. with respect to bootstrapping, other than comparing builds, it helps remove traces of old gcc from build by compiling itslef with newly generated binary:
1st build: gcc 4.6 built with 4.2
2nd build: 4.6 built with 4.6 built with 4.2
3rd build 4.6 built with 4.6 built with 4.6

are you sure you're making use of the new binutils?

libc6 (provided in glibc) in ubuntu used to depend on libgcc1, might still do, so you might have circular dependancies using current build method. what happens if you try to build+boostrap just gcc c compiler, then come back and do c and c++ without bootstrap after glibc?

make sure libtool using correct paths after gcc build. it might still be hardcoded to old version of gcc.