Eclipseの「Debug As ...」メニューを選択してもデバッグモードで起動できないなぁと思ったときは、「WIndow > Preference」でPreferenceパネルを開いて、「Run/Debug > Launching」の項を確認してみましょう。

ブレークポイントがない時の設定が「Never」になっていると、選択項目にAndroid Applicationが出てこないようです。

Preferenceパネル