How do I format a hard drive with a corrupted partition table?

Hi guys,
I have a laptop running windows XP Home and Ubuntu linux on seperate partitions. Somehow the partition table has become corrupted, probably due a to bad linux live cd boot. Now I can't boot into windows or linux. I have decided to format the hard drive, (probably an extreem measure but there isn't really anything on it I want to keep) but booting partition magic 7.0 tells me I have a partition table error #110 and won't let me format the drive. So how can I format this hard drive? How easy is it to repair the partition table? By the way the laptop has no floppy drive.