It sounds like your dual-boot config is "sub-optimal", that you may be sharing
/boot between Fedora and Ubuntu and are using one grub (Ubuntu's) to maintain
two lists of installed kernels. They will never be in sync.
If you want your dual boot to be more manageable, I would recommend re-installing
grub on Fedora to install to a "partition" (e.g. separate /boot partitions) and not the MBR, then from Ubuntu who is the primary bootloader (in MBR) will "just boot Fedora" and it's kernel config/grub will take care of itself.
If you're trying to use a Fedora kernel on Ubuntu, which is
no different than installing a custom kernel from scratch, is highly discouraged.
Now I haven't done this in a while so you might have some tinkering to do.
To accomplish grub move, from Fedora you have to run 'grub-install /dev/sdX' where X is the partition that contains /boot for the Fedora kernel. If this is co-resident with the Ubuntu /boot then you'll have to move it and create a new one.
Then from Ubuntu, edit /etc/grub.d/40_custom and add something like this.
# Boot Fedora's grub from partition
title Fedora OS
root (hd0,2)
kernel /boot/grub/core.img
That (hd0,2) assumes your Fedora /boot is on sda2, adjust that according to your installation.
Run update-grub and it should "just work". Now that Ubuntu's grub simply has a pointer to Fedora's grub, whenever Fedora upgrades the kernel, it can do so without being thwarted by the Ubuntu, which maintains the grub menu list. Each OS will maintain it's own grub and they'll live happily ever after. You should never have to run update-grub again from Ubuntu to reflect kernel updates in Fedora.