Este é provavelmente um problema de rede.
Mas encontrei uma solução alternativa:
- Usado o aptitude em vez do apt-get para instalar as dependências do rbenv:
sudo aptitude install autoconf bison build-essential libssl-dev libyaml-dev libreadline6-dev zlib1g-dev libncurses5-dev libffi-dev libgdbm3 libgdbm-dev