New harddrives need to be made active before they can be seen by the installation program.

Go the new HDD manufacturer's website and download their utillity program.
This can be downloaded as either a floppy drive application or a CD boot disc.
The floppy is the easiest and all but not all computers have floppy drives anymore. There will be instructions for downloading it and how to "make disc"'

Install the new drive in your computer and boot to the floppy/cd utility(be sure to change the boot order accordinly)The application will install and find the new drive...just follow the prompts and it will set up and make the drive active for installation.

When done remove the utility disc and reboot...enter the bios to change the boot order to CD first and insert the restore discs and reboot the computer. Follow the promps and it should put everything back as when you first got the computer!