My solution to this problem was found at http://gems.github.com/
When I got this error my gem source was only set to: http://gems.rubyforge.org/
But the gem I was trying to install was housed on github. So I just needed to add github as a gem source.
$ gem sources -a http://gems.github.com
To find out your gem sources type in
$ gem sources