What do you mean Partition Magic can't create a new partition?
Here's what you need to tell us:
Will you have 1 or 2 operating systems on your computer(Linux and another Linux, Linux and Windows, etc) or is it strictly Linux?
How many hard drives do you have?
How much memory do you have?
When setting up Linux(this could be made easier in RH9, I'm not sure, the last RH version I used was 7.3), you should also have handy what monitor model you have if you can(if you can't, then you should know what the maximum resolution is or the one that you intend to use most often)
and
What soundcard you have
If it's strictly Linux, then I would create two partitions on the Primary Hard Drive(the first one on the list, going top to bottom), the first would either be 2-3x the amount of memory you have(if you have 512 or more, it's best to just make a 1GB partition then, any more space isn't really needed)
Then have your second partition be formatted as either EXT2 or EXT3. I prefer EXT3 over 2, but it's your call.
If you plan on using two OS's, and wish to have them installed on the same hard drive(I can only see why you'd want to have both on the same hard drive if either you only have one or your secondary/other hard drives aren't large enough to install Linux(In your case, RedHat.)
If you plan on doing a dual-OS system and wish to install both on the same hard drive, then tell us how much space is available on each partition on your primary hard drive.
If you only have 1 partition on your primary hard drive, and it's for Windows, make sure you have enough free space available to create the second and third partition(s)
*Note* If you have two hard drives and wish to have both OS's on your primary, then I would recommend only having 1 Linux partition on your Primary, and have your Swap partition as your first parition on your Secondary hard drive)
Continueing for 2 OS's on Primary Hard Drive:
Defragment your Primary Hard Drive, all the current partitions that are on it.
Use the Split option in Partition Magic and create a new partition AFTER your FIRST partition, and give it as much space as you wish(If you don't plan on installing too much more on Windows, I would leave 300MB-1GB free on the Windows Partition(around 300-500MB on the parition where Window's Swap file is located, and the rest on where you install stuff or save files)
If you have multiple Windows paritions on your first hard drive, then you can use the Split option again, then merge the space with preceding partition, and repeate those steps until you add that extra space into your Linux partition.
Note: If you have your Linux Swap partition on your Primary Hard Drive, then you will want TWO Linux partitions, the first would be the size I suggested above(for swap space), the second would be the remaining space. Set Parition Magic to do it's job, then come back once it's finished.
If you have another Hard Drive and wish to have a Linux partition on there as well, you should defragment that hard drive, then split accordingly and merge if needed. The placement for this partition is not as important as the swap and the primary Linux partition.
Here's the easiest, and most say best, way of setting up Linux partitions, however:
Either A) Completely trash Windows(do this by deleting all of Windows's partitions), then create your Swap partition(file size suggestion above) first, then your primary Linux partition.
Or
B) Dedicate a whole hard drive to Linux. This way you can have Windows on one hard drive, with Linux on the other. This is also not a bad idea because if one hard drive gets damaged later by who-knows-what, could be electricity, could be mechanical failure because it was made poorly, whatever, you can use the other operating system, which is on the other hard drive.
When you dedicate your second hard drive to Linux, set it up how you would as if it were your first hard drive.
RedHat also includes fstab, which is a partition/formatting program. I would use Partition Magic first, however, since fstab can't split partitions. but once you have all of your space alloted, I would reformat using fstab, just as a precaution. This also allows you to choose from many types of format, such as Linux Swap(#82), EXT2 or EXT3, or many other formats.
Just be careful where you choose to install Linux(as in, which partition), and if you wish to have multiple partitions for Linux, as in 2 other than for swap, then you will have to choose sooner or later where you want to mount your other partitions(as in, what folder do you want it to be). I have my system as 192MB for Linux Swap, the rest of my 11 or 7GB hard drive for Linux mounted as /(the Root, or the C:\ in Windows terminology), then I have my 2.49GB hard drive mounted as /home, so it stores all of my user settings and documents, less my HTML ones, but I could set up my computer to have a separate partition formy webserver, but it's not practical for me, it would only waste empty space.