does the drive show in bios?
Hard drive manufacturers often have a utility for low level formating theirs drives, more than likely to run in DOS. Also theres a boot CD floating round "Hirens boot CD" which includes a lot of these drive tools.
And just to make sure, when using cfdisk you do put the device with it. eg: "cfdisk /dev/hdb".
Does knoppix come with qtparted?, Ive never used it but looks like a nice tool.
Im no linux guru, so hang around for more suggestions.