Installing rubygems after ruby doesn't cause eselect ruby set X to be called, and hence the usr/bin/gem symlink isn't automatically generated after the ebuild has installed. One has to run eselect ruby set X manually to get this symlink (and hence gem can be found by configure and the like). I suggest adding a pkg_post_inst function which calls eselect ruby in the right way to make sure the gem symlink exists after installing rubygems.
What version of rubygems are you using? I have added such a feature in 1.3.6-r1.
Weird, I installed it on a virgin system and got this problem. I now did the same on another system and there it works. Indeed calls eselect ruby. I don't have the logs any more, so I can't check what went wrong. I'll assume some earth beam or whatever for now. Sorry for the hassle.