Follow the instructions on how to permanently wipe your drive.http://www.cyberciti.biz/faq/how-do-i-permanently-erase-hard-disk/
Linux shred is a DOD grade shredding utility that will make any data on the disk completely unrecoverable.
Depending on the condition of the drive, it is a weak drive, shred will let you know if it will fail for sure. It's pretty abusive.
Once the drive has been "shredded", you can reboot to your recovery CD, and if it is in good shape, you can go ahead and perform your restore.