If I were you, I would try the boot-repair disk. It always repaired my broken boots in one click. Unfortunately, sourceforge is currently down, and I'm not sure you can download the disk.
Edit: if you have a live ubuntu disk, you can run boot-repair as explained here.