FIPS is a utility that will reduce the size of your
windows partition, to make room for more partitions.
People use it when their system has windows
occupying the whole drive and want to make room
for linux. It doesn't sound like this is what you want,
since you already have free space, and only need to
create the appropriate partitions in that space.

When it tells you that the last cylinder is occupied, it
means that there is a hidden file at the end of the
windows partition that FIPS is unable to relocate,
but this is irrelevant unless you really needed
to go ahead and reduce the size of your Windows
partition.

Go ahead and boot the redhat install CD, and see if it will
create the partitions you need. Take care to choose custom install
and, when you get to the partitioning, leave the windows partition intact
and have LILO include windows as a dual boot option.

If the redhat install program won't delete the old linux partitions
and create new ones, then you may have to do something more
drastic, like nuking the entire MBR and starting over
with a fresh installation of windows, and linux.