I recall i had another Gem constant missing error soon after i
upgraded to hardy. I didn't have time to trace the problem down, so
i removed the rubygems pakages through synaptic, downloaded the
current version from rubygems.org <http://rubygems.org>, and
re-installed with setup.rb. It's been humming along ever since!
even all the ninja ubunteros i know recommend installing rubygems via
source, not apt, mostly cause there are upgrade issues if you install
via apt, and try to upgrade via rubygems. So uninstalling the apt
version and reinstalling via rubyforge is the way to get gone. The only
real issue is that you'll have to pay attention to when you do upgrades,
but you'll get the hang of that.