Acontece, depois de cavar através de todos os Links Postados para mim aqui, A resposta para minha pergunta (Só para ter certeza, o Grub deve ser instalado no Ubuntu HD durante a instalação, não o Windows HD correto?) e solução para meu problema é:
Sim. Instale o GRUB na partição do Windows. Então, se você está tendo esse mesmo problema e tentou de tudo, exceto para instalar o GRUB no seu Windows HD, tente isso. É exatamente o que funcionou para mim.
Obrigado pela sua ajuda e links para todos!