Ugh, this one was always a tough one. If your using an OEM OS (like one that came from Dell, Compaq, etc.) then you'll need a new to purchase a new OS disk.
As far as reformatting goes, i didn't think so. Ive installed alot of new major parts and windows didnt freak out. I think you should be fine in this area. Windows should just pick up the change and be OK. I have a system very similar to yours, so if I get my stuff before you, I'll let you know if it works.