Mac OS X ユーティリティが開かない

OS X Lion：Lion 復元について

http://support.apple.com/kb/HT4718?viewlocale=ja_JP

に、

注意：ログインウインドウが表示された場合、または自分のデスクトップとアイコンが表示された場合は、「command」キーを押しながら「R」キーを押すタイミングが遅れた可能性があります。再起動して、もう一度試してください。

と記載があるので、タイミングの問題かもしれません。

Shiftを押さえて起動するSafe Bootを覚えると便利です。ディスクの修復、Font Cacheの消去、Shared Cacheと/usr/libのリンクの修復を行いますので、終わったら再起動します。(最低限の機能拡張しか読んでない為)

特にShared Cacheと/usr/libのリンクの修復は特定の機能や設定がCrashする、反応しないが直る場合がある。/usr/libには沢山のSymbolic linkがありますが、リンク元は僅かのFileにリンクで動作を切り替える大切な役目をします。

Mataoさんも書かれていますが、キーは起動音が鳴ってから押し下げていますか？

押し下げのタイミングは、「起動音が鳴ったらすぐ」（起動音が鳴ってから鳴り終わるまで）です。

起動音が鳴る前に押し下げると、ワイヤレスキーボードの場合は認識されませんのでご注意を。

・・・それでも起動できないときは、Recovery HDが正しく作成されていない可能性も。

オプションキー押下での起動でも該当パーティションは表示されませんか？