Install libreadline:
Copysudo apt-get install libreadline-dev
sudo apt-get install libreadline-dev
Reinstall the ruby and tell rvm where to find readline
Copyrvm reinstall 1.8.7 --with-readline-dir=/usr/include/readline
rvm reinstall 1.8.7 --with-readline-dir=/usr/include/readline
Make sure you get a huge cup of tea before running the command above! It will take some time.