I'm not sure what this "Advanced options" you refer to is; I don't recall such a thing on my GRUB menus. Is this something in your motherboard's firmware? If so, it could be that GRUB has gotten "lost" from the firmware's NVRAM. (Under UEFI, the NVRAM holds boot loader data and the firmware can present its own boot manager menu. Unfortunately, most firmware implementations have pretty awful boot managers. This system also means that if the NVRAM gets reset or changed, your boot loader may fail to launch.)
You can edit your firmware's NVRAM boot loader settings with the efibootmgr utility in Linux. You can use it something like this:
sudo efibootmgr -c -l \\EFI\\ubuntu\\grub.efi -L Ubuntu
This adds the boot loader stored at EFI/ubuntu/grub.efi on the EFI System Partition (ESP) to the NVRAM, giving it the title Ubuntu. You might need to change these details for your system, of course. Note the use of the doubled-up backslashes as directory separators; this is a requirement. Ordinarily, Ubuntu mounts the ESP at /boot/efi, so this example would add the Linux file /boot/efi/EFI/ubuntu/grub.efi as a boot loader. Check to see if this file, or one like it, is present on your system.
Since you say you're using a UEFI-based computer, you should not install the grub-pc package, as Kalle Elmér suggested; that's the BIOS version of GRUB, and if your system is (or was) booting in UEFI mode, installing the BIOS version of GRUB will at best do nothing useful and at worst it will create a mess that will be harder to fix.
Ubuntu, with Linux 3.5.4-030504-generic? – LovinBuntu Oct 9 '12 at 7:23Ubuntu, with Linux 3.5.4-030504-genericentry should do the same as theUbuntuentry. Please report the bug here, and tell us the link to the report so that we can follow-up. – LovinBuntu Oct 22 '12 at 10:16