Could not find rails (> 0) in any repository

The problem is solved by following the instructions here: Delete Your RubyGems Cache. Here is the secret sauce:

gem env
#which will give you something like this:
RubyGems Environment:
  - VERSION: 0.9.2 (0.9.2)
  - INSTALLATION DIRECTORY: /usr/lib/ruby/gems/1.8
  - GEM PATH:
     - /usr/lib/ruby/gems/1.8
  - REMOTE SOURCES:
     - http://gems.rubyforge.org

Next you type the following:

rm -f /PATH/TO/GEM/PATH/FROM/ABOVE/source_cache

Sadly, this was not sufficient for me :(

If you still find that you are getting the Could not find rails (> 0) in any repository error, or the even more insidious:Could not find rubygems-update (> 0) in any repository then you may need to repeat the instructions posted above, then:

gem update --system #for gems 0.8.X or lower
gem update #for 0.9.0 or newer. This is not documented ANYWHERE.

Nearly done! Now you can probably successfully type:

gem install rails

Note that the syntax for the gem update seems to have changed since 0.8.11, and requires you to run without the --system switch. Why this is (and why the --system switch is still listed in the gem help update docs) I have no idea. Good luck!