I built gentoo/linux last week, using gcc 3 (/etc/make.profile -> /usr/portage profiles/default-1.0-gcc3). now, when i do an emerge --update world (after an emerge --clean rsync on the morning or june 3rd), and cannot find gcc-3.1-r5, until i reduce the version number in the line *>=sys-devel/gcc-3.1-r5 in the packages file. and it cannot find texinfo, as that was not installed at all at that point. was not part of the system build. someone who does not know how to play with portage files is going to give up right here.
So you are running a system built from scratch with gcc-3.0 or gcc-3.1? The default-1.0-gcc3 profile is still somewhat experimental, and as such can have changes that could affect running systems. Chances are that you can correct the issues you are having by simply emerging texinfo and gcc-3.1. Since I'm running a gcc-3 system and wasn't bitten by this, I'm going to mark this bug closed, but feel free to e-mail me if you need more help.