To solve this issue, I had to update to the latest version of Ruby, or at least 1.9.3
I run the following sets of commands, from root and it works for me:
apt-get -y remove ruby
apt-get -y install build-essential openssl libreadline6 libreadline6-dev curl git-core zlib1g zlib1g-dev libssl-dev libyaml-dev libsqlite3-dev sqlite3 libxml2-dev libxslt-dev autoconf libc6-dev ncurses-dev automake libtool bison subversion locales-all python libxml2
curl -L https://get.rvm.io | bash -s stable --rails
source /usr/local/rvm/scripts/rvm
This will totally install the latest version of Ruby, then you can run:
gem install RedCloth -v '4.2.9'
RedCloth will now be installed. RVM will manage your Ruby installations. Ruby will now work too.