Mesmo que você tenha dito que você atualizou o Grub corretamente, eu tenho certeza que você não o fez; senão você não estaria tendo esses problemas. Você pode ter seguido as instruções que encontrou exatamente, mas essas instruções podem estar erradas.
Execute o fixmbr do Windows novamente e use o live CD para configurar um ambiente chroot e executar update-grub a partir dele. Eu já publiquei instruções anteriormente .
Observe que, se você tiver uma partição /boot separada, será necessário montá-la depois de montar sua partição raiz e antes de inserir o chroot :
sudo mount /dev/sda1 /mnt/boot
Se depois de fazer isso, o Grub ainda não funciona muito bem com o Windows, isso provavelmente significa que sua configuração do Grub está bagunçada. Volte para o seu ambiente chroot e reinstale os pacotes do grub. Espero que isso resolva as coisas.