Kolla för säkerhets skull med Skivverktyg i debug-läge att partitionen Recovery HD finns där den ska, dvs på din startskiva. Om du skapat en säkerhetskopia av denna partition i Time Machine-disken med hjälp av Assistenten så kan det kanske vara så att det är denna säkerhetskopia du ser efter Cmd+R vid omstart?
Debug/Felsök-menyn i SKivverktyg aktiveras med följande rad i Terminal:
defaults write com.apple.DiskUtility DUDebugMenuEnabled 1
Jag har hållit på och trasslat en del med detta sedan min nya Air fick ett "Prohibited"-fel. Det gjorde att jag fick formatera om disken och installera om hela OS. Inte roligt.