Se a sua instalação Debian usa o GRUB versão 2, você deve executar apenas update-grub como root.
Se a instalação Debian usar o GRUB versão 1, você terá que editar o arquivo /boot/grub/menu.lst config e adicionar manualmente o Ubuntu. Suponha que o Ubuntu esteja em /dev/sda1 , então a entrada será semelhante a esta
title Ubuntu 12.04
root (hd0,0)
kernel /boot/grub/core.img
savedefault
boot