The first option in the Advance Options sub-menu is usually the same as the Ubuntu option. There is something that you can check.
1) At the Grub menu select Ubuntu and press E that will put Grub into Edit mode. Make a copy of the boot parameters.
2) Use Esc to back out and select Advanced options and select the topmost options and again press E. Make a copy of the boot parameters.
3) Compare the 2 sets of boot parameters. They should be the same. You should be getting the same issue with both options.
Another thing to try is to boot into Ubuntu (anyway you can) and run
that is if you only have one hard disk and it is the first hard disk in the system.
sudo grub-install /dev/sda
That will re-write the Grub Configuration files and re-install Grub into the MBR of sda. You machine is not EFI, is it? Other rules may apply.