A partir desse tutorial (que parece estar desativado no momento), estas linhas:
apt-get install build-essential
apt-get install ruby rdoc libopenssl-ruby
Deve ser substituído por:
apt-get install ruby-full build-essential
E tudo funciona bem além desse ponto. Meu palpite é que alguns binários críticos estão sendo deixados de fora ao tentar uma instalação "mínima" de ruby. Resposta obtida por meio da lista de endereços de RoR .