How did you install, using apt-get? You may have better luck if you purge all of ruby and rails and install using rvm. This will also get you a newer version of Ruby I believe. Anyways, first add the key.
gpg --keyserver hkp://keys.gnupg.net --recv-keys D39DC0E3
Then install RVM stable with ruby and rails
\curl -sSL https://get.rvm.io | bash -s stable --rails
It will take a little bit of time to download, configure and install, but after you should have latest Ruby, with rails working.
You can check version with
rvm -v
You can check ruby version with
ruby -v
And you can check rails with
rails - v
I just set this up myself and it installed Ruby 2.2.0 and Rails 4.2.0
For more info see:
https://rvm.io/rvm/install