Eu cometi o mesmo erro há não muito tempo atrás, eu usei um disco de reparação do Windows 7 para fazer meu PC funcionar novamente (você não mencionou se tinha uma configuração de inicialização dupla, a exclusão da partição quebrou o OS para me), em seguida, acrescentou o Ubuntu de volta. Eu percebo que esta pode não ser a melhor solução (e pode não ser válida, pois suponho que você tenha o Windows 7), mas funcionou.