One problem could be that only a certain number of Primary partitions (4, I believe?) can exist on a hard drive in order to be of use to most operating systems. Are any of your partitions Extended?
Also, of what type (ext2, ext3 [or Reiser, same thing], etc.) is your "linux partition", and what command/software did you use to create it? Partition Magic is great for setting up initial partitions, even for Linux. But beware: once you have Linux installed, don't use Partition Magic to play with that partition. It will screw it up!
Last thing: this may be why everyone says to install Windows first if you're looking to run a dual/multi-boot machine. I know in my case, once I installed Linux, I had a lot of trouble getting a Windows OS to install.
If it's a new installation and you haven't devoted a lot of time to customizing the machine or any of yor OSes, I would recommend starting clean again, and installing any Windows-based OSes first before moving on to Linux ones.