the "enable large disk" support feature enables the FAT32 filesystem, which is fairly universally supported nowadays; without it, your stuck with FAT16. a FAT16 partition can only be about 2GB in size. Since your ideal config calls for Windows/Ubuntu on a dual boot, you want windows on there first; since setup is encountering errors, your doing the best thing in the situation; formatting the drive completely.
with fdisk, I recommend splitting your hard drive into the separate Ubuntu and windows partitions; on the other hand, the Ubuntu install let's you resize an existing partition and install it into a new partition.
You are definitely on the right track, though; I'd use fdisk to delete all partitions (assuming you haven't any important data that hasn't been backed up) and recreate them; then reboot and try to install windows again.