Inicialize com um Live CD e verifique sua partição Ubuntu com o Gparted.
Para fazer isso:
- Clique com o botão direito do mouse no partiton do Ubuntu e clique em Desmontar, se a partição estiver montada
- Clique com o botão direito do mouse no partiton do Ubuntu e clique em Check
- Clique no botão de marca de seleção verde ("Aplicar todas as operações")
Isto irá verificar e corrigir quaisquer erros do sistema de arquivos na sua partição Ubuntu.
Se os passos anteriores não funcionaram, então consulte este post para instruções fáceis sobre como reinstalar o Grub.