This link is a good place to start: https://help.ubuntu.com/community/Re...tallingWindows
It discusses Grub and how it works with and without Windows as well as providing detailed instructions on several methods of recovery. It sounds as if something didn't quite go right in the initial installation because normally, Linux and Windows make nice neighbors, provided Linux gets installed second.
Ubuntu has different releases that go by names and numbers. For example, 10.04, 10.10, 11.04 and get called things like Karmic Koala, Lucid Lynx, Natty Narwhal, respectively. The update manager will run pretty much every day and tell you when updates are available. Normally, these won't even require a reboot, unless you update something like the Linux Kernel which can't be stopped and started. There is also a distribution upgrade, where you go from say 10.04 to 10.10. These will do a major download and update of the system replacing almost every application. Going more than one step, such as from 10.04 to 11.04 while skipping 10.10 can cause problems. Personally, it has been my experience that about 95% of the stuff works after a distribution upgrade, but there is always something that needs fixing. This is what I meant by distribution version by the way.
Based upon your follow up post, this is relevant because around 10.04 a change was made to use Grub2 instead of Grub, but it also matters whether you did a distribution upgrade, in which case, according to the link above, you probably are still using Grub, or if your first install was from a version with Grub2. You will need to read the link instructions carefully and determine which Grub version you are using because the modification methods are different. For example, I don't believe Grub2 uses menu.lst anymore.