Shoot. OK- here are things to be done:
First off, do you have any important data on the windows partition? If so, boot into it, and copy it onto another HD, or a DVD.
I never got what kind of a mac you have. If it's a portable, an iMac, or a mini- this is going to be slightly more complex. If it's a MP, things are fairly straight forward. I going to assume that you have a machine with a HD that is not all that accessible. If this is the case, do you have access to any other mac? My reasoning behind the question is that you could try booting your machine in target mode- basically you hold down T at startup, and it turns your entire machine into a giant external hard drive. You can then attach it to another mac via firewire, and this should let you go into that other mac, and use disk utility on it to format the HD on your mac. If you don't have access to another mac things get even more complicated. You have a choice, and it's up to you from there- basically you'll need to get that hard drive out of your machine, and attach it to an external enclosure (about $20), and use another machine to rebuild the partition (this can be a windoze box). This is a hit and miss, as we really don't know how far your drive is gone. You risk A)- voiding your waranty (unless you have a MacBook, or a Pro tower), and you could be out $20 if the drive is that gone. One upside to this, is that if the drive is totally screwed, once it's out of your mac, you can go down to the store, get a new one and have your computer back in working order within 30 minutes. Your other option, if you don't have a second mac, is to take it down to an Apple Store (if there is one near you), or an Apple Service center, and have them try to get the drive to work. Depending on when you bought the computer, it should still be under waranty. If nothing else, they'll be able to tell you how damaged the drive is (I'm guessing that it's still just a bad FAT). If have a MB or if you are one of the lucky ones, and are sitting in front of a mac pro, then the drive situation is not as dire. Those two computers have user- accessible HDs, and if push came to shove, you can just pull them, and get new ones.
I won't lie to you- the fact that the CD is not seeing the drives is not a good sign. DiskUtility should have been able to recognize its own components.
SHOOT- stop! I just had a brain fart! Try this- you might be able to rebuild you HD this way:
http://docs.info.apple.com/article.html?artnum=303081
Just inser disk 1, and hold down D. Darn it, I'm not erasing all that other stuff I just wrote! But seriously, sometimes my brain is working in the background... Let me know if that gets you anywhere.