The last I checked, Ubuntu's version of GRUB 2 places a GRUB binary on the EFI System Partition (ESP), which is mounted at
/boot/efi in Linux. The GRUB configuration files (
grub.cfg and various support files) remain in
/boot/grub, which is on another partition. (IMO, this is a bad design, but that's another matter....) Thus, if you use Ubuntu's GRUB binary, GRUB's menu should be updated automatically.
If you installed GRUB from source code, or perhaps from somebody else's binary, though, it could work differently, with
grub.cfg and its support files on the ESP along with the GRUB binary. This setup is actually safer, but Ubuntu's scripts don't support it, so you'd have to manually update things after every kernel update. From your description, you seem to have this setup, although the site to which you linked seems to describe setting it up using Ubuntu's binaries, which is a puzzling inconsistency. Did you try something else at some point, or deviate from the site's instructions to get it working? You could test by making a change to the description of a boot option in one of the
grub.cfg files (assuming you've got two of them) and seeing if that change appears in GRUB's menu when you reboot.
Assuming you really do have a GRUB binary that looks on the ESP for its
grub.cfg file, there are a number of possible solutions, including:
- Install Ubuntu's version of GRUB over whatever you've got now. This is risky because it might not work, and could therefore leave you with an unbootable installation. (Your initial description says that your initial installation in EFI mode was unbootable, which suggests you might have a problem with Ubuntu's version of GRUB.)
- Switch from GRUB to another boot manager/boot loader as your primary boot program. I describe several here. My own rEFInd is likely to be easy to get running, and it will handle kernel updates automatically. There's some risk of creating an unbootable installation if you try this, but the risk is less than that of replacing your working GRUB with another one, since you should be able to use your firmware's boot manager to boot via GRUB even if the new boot program fails completely.
One more comment: New computers invariably ship with Secure Boot active, which creates an extra hurdle to overcome. Ubuntu 12.10 and later come with Secure Boot support, but that doesn't always work. Most third-party boot loaders, including rEFInd, require extra work to get working with Secure Boot. Thus, if you haven't already done so, I recommend you disable Secure Boot in your firmware. If you want to boot with Secure Boot active, it's better to enable it after installing your boot loader, since you'll be able to test the boot loader without Secure Boot first, and then add Secure Boot to the picture and debug it with the knowledge that your basic boot loader configuration is working.