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
You can check ruby version with
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: