F2VodIInさん、まさにUEFIが原因です。
どのように試行錯誤したか覚えていませんか？

実際にはハードウェア的な事もしていますが、結果的にそれでは復帰しないので作業する事は2つだけです。
(私のG580にはubuntu 12.04.1 LTS 64bit版しかインストールされていません。)

手動でubuntuのUEFI boot entryを削除する。
boot-repairと言うgrubを操作するアプリケーションで回復する。

だけです。

注意!!
どの時点で"setup" の項目が出る様になったのか定かではありません。
作業途中でUEFI boot entryの削除をする為、一時的にハードディスクからの起動ができなくなります。
最悪回復できない場合もあるかもしれません。
自己責任でお願いします。

1. Ubuntu Secure Remix LiveCDを作成する。(再インストールせずに復旧する為の下準備です)
以下のページの中のGetting Ubuntu Secure Remixにあるリンクから、使っているubuntuのバージョンに合わせた64bit版LiveCDをダウンロードする。
(現状では12.04.1版と12.10版がある)

https://help.ubuntu.com/community/UbuntuSecureRemix

ダウンロードが終了したら、DVD-RかCD-R(容量的にDVD)に焼いて、そのLiveCDで正常に起動できるのを確認しておく。
LiveCDなのでインストーラーが起動するが、日本語を選び"Ubuntuを試す"を選択すれば良いです。

2. UEFI boot entryから"ubuntu"を削除する。
(ここは危険な操作です。ハードディスクから起動できなくなります。)
ハードディスクからubuntuを起動し、UEFIのブートエントリーとブートオーダーを調べる。
grub-installスクリプトでも使われている"efivars"モジュールと"efibootmgr"コマンドを使うが、man pageの通りには表示されない。
それどころか何も表示されないので、結局grub-installを実施して表示されたエントリーとオーダー番号を使いました。

$ sudo grub-install

私の所ではubuntuしかインストールされていないからか、どちらも"0000"でした。

"0000"となっていたので、実際に削除する。

$ sudo efibootmgr -b 0 -B

再起動すればboot entryが消えていてハードディスクから起動出来なくなっているので、F12でメニューを出しTABキーで"App Menu"を確認してみる。
(私はずっとF2しかBIOSには入れないと思っていたので、この時はF12を確認していません。)

3. UEFI boot entryに"ubuntu"を復旧させる。
最初に作成したUbuntu Secure Remix LiveCDで起動し、ランチャーに登録されているboot-repairを起動する。
ネットワークを設定してインターネットに接続できれば起動時に最新版にアップデートしてくれる。
起動したら表示されている"高度なオプション"をクリックし、内容を確認して問題無ければapplyする。
(ハッキリ覚えていないんですが、特に何もオプションは変えずに確認だけしてapplyしたと思います。)

これで復旧されるので、再起動してF2の挙動やF12からの"App Menu"を確認する。
私はここで、F2しか確認していませんし、結果としてF2ではBIOSに入れない。
予想としては、ここでF12からTABで"App Menu"にいくと"setup"の項目が現れていそうです。

これ以降はハードディスクから立ち上げて、念の為にgrub-installやupdate-grubを実行し、F2でBIOSが起動するか確認していました。
しかし、F12の"App Menu"はあまり確認していないなと気づき表示させると"setup"の項目が増えていて、そこからBIOSに入れました。
単なる運で回復しただけかもしれないし、boot-repair後に復帰していたのかもしれませんが、"App Menu"に出るのが正常なのかも解らない状態です。

備考
boot-repairを使った後、/boot/efi/EFIに以下の2つが増えていました。
1. Bootディレクトリ               # bootx64.efiファイルが存在している。
2. Microsoftディレクトリ         # インストールもしていないのに、bootmgfw.efiとbootx64.efiファイルが存在している。

私以外の人でも"F12"からの"App Menu"に"setup"を表示させる事が可能と解ったのは大きな収穫です。
まず、どこの段階で"App Menu"に"setup"の項目が現れたのか教えてください。

1. UEFI boot entryから"ubuntu"を削除した後か。
2. boot-repairを使ってUEFI boot entryに"ubuntu"を復活させた後か。
3. boot-repairを使って復活させた後、ハードディスクから起動してgrub-install等を実行した後か。

"App Menu"にダブってしまう項目が出る件ですが、私の所では以下の様に"setup"を含めて3個だけです。

--- App Menu -----------
| 1. Diagnostic Splash |  <- 1と3でダブっている
| 2. setup                 |
| 3. Diagnostic Splash |
------------------------

もともとは、"1. Diagnostic Splash"しかありませんでした。
boot-repairを何度も実行した結果、9個になってしまったのでしょうか?
私はboot-repairを1度しか使っていません。
boot-repairで増えると言う事は、boot-repair側のオプション設定で何かあるかもしれませんね。
こちらはもう少し調べてみたいと思います。

UEFIをDisableにしてもF2は無効でした。

UEFIパーティションが存在してるだけでダメなのでしょかね?
私はそこまで確認していませんでした。

このトピックはUbuntuその物とは離れてきた感がありますが、もう少し調べてみようと思います。

"App Menu"に"setup"の項目が現れたのは、「1. UEFI boot entryから"ubuntu"を削除した後」だったと思います。（確かではありません。）

これは想定外でした・・・
boot-repairで回復する操作は関係ない事になりましたね。
しかし、納得行かない所もあります。
何故ならば、grub-installスクリプトを実行すると同じディストリビューションエントリーをefibootmgrで削除してから、再度efiboomgrで登録する動作になっています。
事実、UEFI boot entryにダブっていた"ubuntu"のエントリーはgrub-installを1回実行しただけで1個になりました。
最初はF2の動作ばかり気にしてF12をあまり確認していなかったから気づかなかった可能性はありますが・・・
もしかしたら、UEFI boot entryにOSの登録情報が無い状態で再起動すると"Setup"の項目が現れる可能性もありますね。
既に"Setup"が出てしまっているので確かめようが無いのが残念です。

"App Menu"の項目が増えるのは、「efibootmgr」でentryを削除した時でした。（今は１0個に増えてしまいました…。）
また、UEFIパーティションが存在していなくてもF2は無効でした。
さらに、UEFIを無効にすると、もちろんOSは起動しなくなりますが、CDブートもできませんでした。結局、有効にして再度インストールしました。
おそらく、"App Menu"の項目は、増えることはあっても、現状では消すことは出来ないのではないでしょうか？

この辺りはBIOS側の問題な気がします。
BIOSの書き換えツールやBIOS自体のアップグレードが提供されるまで解決できそうな気がしません。
しかし、Windows8が発売され、Windows8のUEFI boot managerからBIOSを呼び出せるらしいので、問題にする人が居なくなってくる可能性が大。

ちなみに現状で私のG580(2689-7LJ)のBIOS情報は以下の通りです。

version: 62CN34WW
date: 04/26/2012

内容が翻訳を使っている様な感じなので、うまく伝わるといいのですが・・・

* "F12"を押してデバイスの起動画面にOS(ubuntuとかWindows等)の名前が登録されていますか？
そのまま"TAB"を押し"App Menu"に切り替えると、項目に"setup"と表示されていますか？

OSの名前が登録されていて"setup"が表示されていない場合は、同じ現象だと思います。
"F2"を押してもBIOSを表示させることはできません。
"setup"が表示されていれば、そこからBIOSを呼び出す事ができます。

* BIOSを表示させる為には、"F12"のデバイスの起動画面からOSの登録を削除しなければなりません。
しかし、それを実行するとHDDから起動出来なくなるので準備が必要です。

* 使用しているPCの状態を教えて下さい。
windowsとdual bootでubuntuをインストールしている？
Windowsをrecovary領域を含めてformatし、ubuntuをインストールしている？
"F12"の画面で登録されているOSの名前は何ですか？

いつのまにかLnovo G580(2689)シリーズにもBIOSアップデートが提供されていました。
修正内容は1件のみで、以下となっています。

Fixed:
1. Fix issue: BIOS and boot menu can't be accessd after windows recovery

になっているので、F2でBIOS画面が表示できない件や、小手先で"App Menu"にBIOSを出す項目を出現させた為に発生した弊害("App Menu"の項目が重複して増える)が直りそうな感じではあります。

但し、提供されてるユーティリティーが何故かWindows8版のみ・・・・
Winodws7プレインストールPC購入者はイヤでもWindows8にアップグレードしなければ適応できない?!(Windows7でも動くのだろうか)
(私は何れWindows7版やDOSのISOイメージ版が増える?w と言う希望的観測をしてますw。)
自分はUbuntuしかインストールしていませんし、Windows7プレインストールモデルなので適応していません(正確にはできない)が、一応情報として書いておきます。