Essa é a única solução que eu conheço (ou pelo menos a mais fácil) ... liberar espaço e instalar janelas, mas como você mencionou, você precisará restaurar o grub. Você pode fazer isso de um CD ao vivo.
Restaurar o grub tornou-se uma tarefa muito simples, confira a forma gráfica no link a seguir link