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.