Fresh install w/ Recovery Disk Stalls

I have an HP Pavillion m8000 that the hard drive crashed. I bought a new Seagate Barracuda hard drive as well as factory recovery disks directly from HP. The problem I am having is when I run the recovery disk it stalls at the check box for software load. Does anyone have any ideas on how to get past this point. HP support told me to get DISKKill and run it and then run the recovery disk. Same problem it seems no mater what I do.
Thanks,
Rich