I'll give a helpful answer. Obtain a Windows disc and run diskpart from the recovery console. The Command is as follows:
Diskpart {Press Enter} Select Disk 1 {Press Enter} Clean {Press Enter}. Will nuke all partitions and MBR.
Edit: Yes, changing the HD would get rid of it also.