Depending on the box used for the VM, the version of RubyGems might need updating. On the first attempt trying to install the Sinatra gem, I received the following message:
WARNING: RubyGems 1.2+ index not found for: http://rubygems.org/
Well 1.2 is out of date, let's fix that:
$ sudo gem update --system
On the second attempt, I got this error: