Вы используете RVM?
Если это так, вы можете переустановить ruby, указав местоположение вашей установки openssl:
$ rvm remove 1.8.7
$ rvm install 1.8.7 --with-openssl-dir=/usr/local/openssl # or wherever openssl is installed
В системе на основе Debian вы можете узнать, где установлен openssl, выполнив следующую команду:
$ dpkg -L openssl
В качестве альтернативы вы можете установить RVM для вас openssl:
$ rvm package install openssl
$ rvm remove 1.8.7
$ rvm install 1.8.7 --with-openssl-dir=$HOME/.rvm/usr
Обратите внимание, что после этого вам потребуется переустановить рельсы:
$ gem install rails