Also, since there is no indication that NTFS is even a problem but has been brought up, if there are multiple NTFS partitions (not sure that this is an issue either but want to address the solution just in case), FDISK generally can't remove extended NTFS partitions.
But for that there is a DOS based, somewhat GUI interface, program from one of the NT service packs that can remove these as well. Made it available at:
http://www.onecomputerguy.com/delpart.exe
So just delete whatever partitions you need (if you need to), correctly create any partitions you need (if you need to), then format away.
Again, the details for how to do this have been previously posted. Hope this helps solve yet another potential situation.