1) Insert your Redhat install CD one last time and bootup.
2) When it gets to the installation screen, hit <CONTROL><ALT><F2>, this will take you to a second term.
BTW, you can skip these two steps if your linux is still bootable.
3) So, either in the installation terminal, or in a "normal" term with you "su"ed to root (type in "su", enter, your root password, enter) type in "fdisk /dev/hda"
Now it's my understanding that your hard drive is toast, if not it will be... So, Backup first mebbee?
4) With fdisk running, hit "p" then enter. This will print out the current partition list.
5) Hit "d" followed by the partition number, lather, rinse, repeat until you have deleted all of them.
6) This is the "are you REALLY sure"
step, if so, hit "w" to write the changes to the partition table.
7) Cycle power, re-install Windows, live long and prosper.
If it still doesn't work, then please do what MasterC suggests and post your partition table for all to see.
As for hidden partitions, they exist to be sure, but mostly for Windows (none for linux).
But you can still create and delete even these partitions in linux. So I really don't think that this is the problem.
And don't get all of this confused with wiping out the bootloader which would require DOS's (ok, Windows) fdisk. Like this: "FDISK.EXE /MBR" (usually from a bootable floppy).
BTW, I'm having you use your Redhat CD since I'm pretty sure that you still have it. If not, then you will need to get something along the lines of a "Tom's Root-n-Boot" rescue disk. (http://www.toms.net/rb/
) The Windows FDISK won't delete non-DOS partitions.