自分の環境で成功した方法を記載しています。
##１.ユーザーローカルなディレクトリにrbenvをインストールしている場合

git remote -v
fatal: Not a git repository (or any of the parent directories): .git

不幸にも上記のようなエラーが出てしまった場合。
勝手な想像だがこのようなエラーが出るのはgit clone をhttps経由で行なっている場合に発生するのではないかと思う。
以下の手順でruby-buildをインストールし直す。

cd #（ホームディレクトリにファイルをコピーしている場合が多いためホームヘ）
rm -fr ./ruby-build
git clone https://github.com/sstephenson/ruby-build.git
cd ruby-build
sudo ./install.sh

##２.全ユーザー共通で使用しているrbenvを使用している場合

全ユーザー共通でrbenvを使用する方法の参考
http://qiita.com/nekogeruge_987/items/2e73be2ffb105c28ffad

上記方法でインストールしているrbenvでrubyを管理している場合
pluginsにインストールしているruby-buildが古いと新しいrubyが参照できないので更新する必要がある（はず）

以下方法
pluginsのディレクトリへ移動しruby-buildディレクトリ削除、その後ruby-buildを入れなおす。

cd $RBENV_ROOT/plugins
rm -fr ./ruby-build
git clone https://github.com/sstephenson/ruby-build.git

これで最新のRubyを参照できるはず

rbenv install -l
Available versions:
  1.8.6-p383
  1.8.6-p420
  1.8.7-p249
  1.8.7-p302
  1.8.7-p334
  1.8.7-p352
  1.8.7-p357
  1.8.7-p358
　・
　・
　・

2014/03/19追記　gitを使っているので以下の方法のほうが早いという事に気づいた。

cd /opt/rbenv/plugins/ruby-build/
git pull origin master