現象

$ knife solo prepare root@XXX.XXX.XXX.XXX -i ~Hirata/.ssh/KEY.pem

$ knife solo cook root@XXX.XXX.XXX.XXX -i ~ Hirata/.ssh/KEY.pem
Running Chef on XXX.XXX.XXX.XXX...
Checking Chef version...
ERROR: RuntimeError: Couldn't find Chef >=0.10.4 on XXX.XXX.XXX.XXX. 
Please run `knife solo prepare root@XXX.XXX.XXX.XXX -i /Users/Hirata/.ssh/KEY.pem` 
to ensure Chef is installed and up to date.

knife solo prepare 〜で初期化したサーバにおいてrvmでrubyをアップデートしてgemを使った後にローカルよりcookしたところ、上記のエラーが出ました。

原因

これはrvmとchefのrubyの違いによるものでした。
非常に迂闊でした・・・。
chefはprepareでリモートインストールすると、同時にrubyや一部gemをインストールします。
しかしこれは普通のrubyとは異なり、組み込みのrubyなのです（prepareが終わったあとリモートサーバでrubyと打ってもパスは通っていません）。
なので、その上からyumやrvmで普通のrubyをインストールすると、ラッパー情報（envのパスやrvm.sh）が邪魔をしてしまい、欲しいgemなどが見つからなくなる、というからくりがあります。
従って、今回のようにchefをリモート実行すると、ssh接続のログイン時シェルに従って転送した組み込みruby向けパスではなく普通のrubyとgemのパスを見てしまいます。
その結果、インストールしたはずのchefが見つからないよ？？？と怒られてしまうわけです。

とりあえずの回避方法(1)

とりあえずの回避方法1つめは、普通のrubyを削除して組み込みのみで使うと言うもの。
chef以外でrubyを使わないのであれば、これが一番安全で簡単です。
おとなしくrvmにはseppukuしてもらいましょう。

とりあえずの回避方法(2)

とりあえずの回避方法2つめは、ラッパーシェル(rvm.sh)を変更すると言うもの。
Capistrano3を使う場合などどうしても新しいrubyが欲しい場合は、こうするしかありません。
しかしこれは面倒で危険です。
ここまでしてchefを使う理由はないなぁ、というくらいに大変です。

とりあえずの回避方法(3)

rvmのインストール方法にもよりますが、sudoを使うなどしてrvm.shを読まないユーザでchefを実行すると言うものがあります。
ただし/etc/profile.d/に放り込んでいて無条件に読まれるような設定の場合は、意味が無い場合もありますのでご注意ください。

おそらくの抜本的回避方法

knife solo prepareを使わないでchefや必要なライブラリをrvmとgem経由で入れるというのも理論上できるはずですが、これ一筋縄でいかないんですよね。
現在深く調査中ですが、ここまでするくらいならやっぱりchefなんかｒｙ

最後に

個人的には、rubyを他に用いる場合chefを諦める方がいいと思います。
組み込みと本流で2つのバージョンのrubyを入れるということ自体本来はナンセンスな話ですし。
そもそも、AWSやXenを使っているなら、AMIやイメージと言う単位で冪等性は確保できますし、簡単で安全です。
デバッグ工数とか必要ないですもの・・・。
ソースとして設定を保存したいという気持ちは分からないでもないですが、あまりにも面倒すぎます。