The error you received is really telling you that you don't have enough contiguous space on your hard drive to create a partition for Boot Camp to install Windows. And yes, formatting will destroy the data on your hard drive so you should not do that without first making a backup.
There are several ways you can resolve the error you're getting. One is free the other will cost $29.95. Here's the free method:
1. Make a backup of your entire hard drive using Time Machine. (to an external hard drive) Keep the drive attached to the machine.
2. Boot your machine with your install recovery DVD (Leopard, Snow Leopard) and use Disk Utility to erase and format the drive as HFS Extended Journaled. Make sure you erase and format your MacIntosh HD not the external drive!
3. Install OS X - during the install process you will be asked if you would like to restore with a backup. Select yes and select your backup from the external hard drive. The Time Machine backup will restore everything. After it finishes, reboot your machine from your MacIntosh HD.
4. Run the Boot Camp assistant again.
The other method I mentioned above that was $29.95 is an application called iDefrag 2. You can download it from
here.
Regards.