Eu presumo que a 'nenhuma partição existe' acontece quando você (tenta) inicializar a partir do disco rígido: está dizendo que o Grub não consegue encontrar o lugar onde o restante das coisas necessárias para inicializar é. Isto é normalmente armazenado na mesma partição que o resto do sistema Ubuntu, então se você delectou aquela partição, você definitivamente terá problemas ...
Adicionalmente, se a instalação do Ubuntu foi originalmente Ubuntu 9.10 (Karmic Koala) ou 10.04, ele estará usando a versão mais nova do Grub, Grub2, e eu não acho que seu comando sudo update-grub
funcionará como pretendido com o versão mais recente.
Você pode acrescentar à sua pergunta quais partições e quais sistemas operacionais foram instalados no seu computador? Meu palpite é que você precisa criar uma nova partição para / boot (que provavelmente exigirá uma reinstalação do Grub). ) ou, se apropriado, voltar a usar o mbr do Windows .