У меня была эта проблема со времен апгрейда oneiric. Ядро восстановления загружается прямо в приглашение root без меню.
Я тоже не могу telinit 3.
Похоже, вам не хватает пакета дружественного восстановления.
sudo apt-get install friendly-recovery