When I need to install new gems I start off by installing a few packages that can be helpful:

apt-get update;
apt-get install ruby-dev build-essential

If you installed gems like sinatra or rack from the Ubuntu repositories they may be too old to support the gem you are now trying to install. I would then recommend removing any packages like ruby-sinatra and installing them instead via gem install sinatra