Are you trying to install Linux first? I have only ever run a system where Windows was installed first, and it works fine. I'm running Windows 98 SE and Mandreak 7.2 quite happily, side by side.
Mine is as follows:
1st partition: Windows FAT32, 2GB = 'C drive'
2nd partition: Windows FAT32, 2GB = 'D drive'
3rd partition: Linux ext2fs, 1.9GB = Linux Stuff
4th partition: Linux SWAP, 100Mb = Linux Swap
5th partition: Windows FAT32, 100Mb = 'E drive'
I know that this is a silly number of Windows partitions to have when I've only got 1x6Gb HDD, but I regularly 'play' with Windows (and hence my love of Norton Ghost, as mentioned in most of my previous posts). D drive for stuff that I need, and E is for temp stuff (downloads, etc).
Oh, yeah. I hear that LiLo doesn't like being in a partition above 8Gb, and Windows really doesn't like booting from anything other than the 1st partition.
'Fraid I can't be of much more help as I've never come up against a problem like this. Try putting Windows in 1st. Try searching for other posts of a similar nature, I've posted details of how I got my system to work OK.