I was having a variation of this problem; where, for whatever reason, I had lost the ability to compile 32 bit stuff: emerge sandbox failing with "compiler cannot create executables" and the like. After spending alot of time trying things suggested in this and other threads, I finally got everything working again by rebuilding the "system" packages in a chroot. Although this is not a quick fix, I highly reccomend it since it should fix just about any problem I can imagine and it 's easier than a complete re-install. (and do you really want to keep looking through more threads?)

Make a mount point somewhere
Code:
mkdir /mnt/chroot/

Download a stage3 tarball appropriate for your arch/profile and extract it in /mnt/chroot
Code:
cd /mnt/chroot
wget http://gentoo.osuosl.org/releases/amd64/2006.1/stages/stage3-amd64-2006.1.tar.bz2
tar -xvjf stage3-amd64-2006.1.tar.bz2

Now copy in your make.conf and mount some important stuff
Code:
cp -p /etc/make.conf /mnt/chroot/etc/
cp -p /etc/resolv.conf /mnt/chroot/resolv.conf  # you might need DNS
mount -t proc none /mnt/chroot/proc
mount -o bind /dev /mnt/chroot/dev
mount -o bind /usr/portage /mnt/chroot/usr/portage

Important: use your favorite editor to add FEATURES="buildpkg" to /mnt/chroot/etc/make.conf . Also, delete any crazy CFLAGS you were using and any FEATURES that won't work like ccache and distcc. Then:
Code:
chroot /mnt/chroot
env-update && source /etc/profile
USE="bootstrap" emerge -e system

I'm not sure if "bootstrap" is necessary, but that's what I used. Now go to sleep, and sleep soundly because this is very likely going to work. After emerge is done (tomorrow probably):
Code:
exit   # get out of chroot
emerge -aek system

If everything is cool, then your should see something like "[ binary R ]" next to each proposed package. If it is then press enter and in a few minutes your "system" is back to normal!

Note: If you set $PKGDIR in make.conf to something outside /usr/portage then you will have to copy everything from /mnt/chroot/$PKGDIR to $PKGDIR before emerge -aek system .

I know this is a crude, slow and inelegant "solution", but it was the only thing that worked for me.