What I would recommend then even in general would be to zero it out first, that can't harm.
Not sure if that will fix the issue with cfdisk or not, you just have to see; if not, you can then still follow curaga's approach.
sudo cat /dev/zero > /dev/XdX
where XdX is the device of disk, e.g. hda, sda; make sure you get that right.