UPGRADE YOUR GEM SYSTEM TO V 1.1.1 BEFORE ADDING gems.github.com TO YOUR SOURCES!!!
That is the message that needs to be displayed in an H1 tag across gems.github.com, not some tiny note saying "if you get this error, you should" and then a message that essentially amounts to "go back in time and not have done this." They'll tell you to update your gem system, but if you're experiencing the problem, gem can't update itself.
For those of you lacking time machines, you need to remove github.com from your gem sources so the system update will run. The command to remove a source is not documented anywhere¹, but if you promise not to tell anyone, here it is:
sudo gem sources -r
http://gems.github.com/Once you've done this you can now do
sudo gem update --system
sudo gem sources -a
http://gems.github.com/and you're back in business.
¹ EDIT: A reader pointed out that it IS documented. "gem help sources" will get you what you need, and "gem help commands" is listed from the main "gem help" screen so you can navigate to it. Thanks!