I've seen problems like this where booting Windows messes up grub caused by using Dynamic Disks in Windows or converting a Basic partition to a dynamic one before installing Ubuntu. Maybe this initially caused the problem?