This is what happened when I want to install rmagick gem.

username@username-desktop:~$ sudo gem install rmagick
Bulk updating Gem source index for: http://gems.rubyforge.org/
ERROR:  could not find rmagick locally or in a repository

What the hell…
After some googling I found that RubGems 1.1.x is buggy and and update to RubyGems 1.2 is necessary.
To learn your RubyGems version:

username@username-desktop:~$ gem -v
1.1.0


I try to update RubyGems :

username@username-desktop:~$ sudo gem update --system
Updating RubyGems
Bulk updating Gem source index for: http://gems.rubyforge.org/
Nothing to update

After this failed attempt, I realized that RubyGems 1.1.x is really buggy. So I must go on manually to update RubyGems.

Now the solution:

  1. Download rubygems-update-1.2.0.gem
  2. Change your directory where your downloaded gem is. In these example my gem is at Desktop.
    Now you must install rubygems-update-1.2.0.gem.

    username@username-desktop:~$ cd Desktop/
username@username-desktop:~/Desktop$ sudo gem install rubygems-update-1.2.0.gem
  3. username@username-desktop:~$sudo update_rubygems

To check if our process is successful :

username@username-desktop:~$gem -v
1.2.0

If you see 1.2.0, you did it.