I've installed both Windows and Linux (and OS/2) literally hundreds - if not thousands - of times over the last 10 years, and Windows has never complained about the existence of non-FAT partitions as long as there is a FAT partition for Windows to go on. The only time you would see that message is if you don't have an appropriate FAT partition available and have no free space. If you're seeing that, then you most likely have your drives improperly partitioned - like putting Linux on the first partition or something. What does your partitioning scheme look like?
Weird, I always get this message and I've had plenty of practise installing OSs myself and I've never found a way around this problem. I'll give an example to make things clearer.

I had an Intel box with a 30GB HD split straight down the middle with 15GB Win98 and 15GB Linux (Redhat, Slackware, Suse...take your pick, I tried a few of them). I decided to reinstall Win98 because it was having display problems and I got sick of messing around with the driver configs.

So I chuck in my official (I can't believe I actually paid it) Win98SE CD and reboot to reinstall windows. The install program goes ahead and does its thing but before the actual install starts you get a message like, "Unrecognised format on drive whatever". The only options are too reformat to FAT32 or exit the install. One of my friends at work who is an experienced sys admin says exactly the same thing.