Could not find rails (> 0) in the repository

If you get this when trying to install rails with rubygem you apparently need to remove your source cache.

Not totally obvious.

Update: As you can see from the comments re-running the command should solve it for most.