The first question that comes to my mind is "Why do you want to format your drive?". Since I suppose you do not wish to have an unformatted computer lying around, you are going to install something else later on, be it Windows or another Linux. In either cases, you'll need CDs to install from, which have partitioning tools in them. So you may try to download a CD from your Lindows, burn it and boot from that.
Also are you sure that the "only" CD you got is bootable? If so you have probably misconfigured your BIOS, probably when setting the boot order of drives. The first drive that is to be read has to be the CD, and then the Harddisk. You'll need to make a similar tweak if you want to follow XavierP's advice with the boot disk, by giving the floppy drive a more important priority then the harddrive.
Last but not least, it is quite understandable that fdisk didn't work from Lindows. You cannot partition the drive you use. You need to boot from another distro, possibly a "live" one. If you want a practical solution for your partitioning needs, I recommend using PowerQuest's PartitionMagic software. It comes with two floppies that you can boot and do anything you fancy with your drives. If you do not wish to expend any money on that, I'll be happy to send you mines..