eu li em um forum que você precisa entrar no ubuntu e montara partição do fedora e depois rodar o grub-update, fonte: http://forums.fedoraforum.org/showthread.php?t=279221