ubuntuでcurb(curl)を使うには

libcurl4-gnutlsをインストールする必要があります。

sudo apt-get install libcurl4-gnutls-dev
sudo gem install curb