You deleted all the partitions, but you didn't touch the Master Boot Record (MBR). If you want to clear it, boot off of a Linux rescue disk and do:
dd if=/dev/zero of=/dev/hda bs=512 count=1
This overwrites the first sector of the hard drive (which holds the MBR) with zeros.
Alternatively, you can just go ahead and install the OS you want and let it overwrite the MBR>