Results may vary. Using GParted I resized my windows partition (C:\ - /dev/sda2). I also moved it to the end of the drive.
I then resized my "windows-boot" partition (/dev/sda1). The one that Windows 7 made during install.
I don't remember why I resized this partition, but I did.
And then I proceeded to install Ubuntu 9.10 with one swap partition and one ext4 partition for root. Both of these together used up the space on my harddrive between my windows partitions.
Finally, when I tried to boot into windows, I got the error message that I believe you are describing. Unfortunately I cannot recall its exact wording.
I simply put the Windows 7 CD in as it requested, booted with it, and followed the on-screen instructions to run the repair.
After doing so I still had grub, Linux and Windows both worked.