My USB/Firewire Hard Drive was partitioned in 100% Mac OS Extended. I used Partition Magic to see if I would be able to shrink that partition around what was saved and partition the drive into partially NTFS so I could easily use it on my PC and Mac. However, Partition Magic could not recognize Mac OS Extended, and I ended up deleting the data (it was all replaceable, except for a very important video. We may still have the tape, and I hope we do). Therefore, I would like a partitioning tool that could shrink the Mac OS Extended partition, create an NTFS partition, and a 32gb FAT32 partition for sharing files between the Mac and Windows.

If you just use a FAT16 or FAT32 format, both computers will be able to read the files. I have my USB drive formatted in FAT32 right now and I carry it between my Widows at home and the Macs at school for video editing and both read it fine

Yes, but the problem is that my current tool on the mac does not allow FAT32 and I already have put a significant amount of files on the HDD (about an hour's worth of transfers via firewire). I need to make a new, PC-only partition and a FAT32 partition without damaging the existing Mac OS Extended partition.

Oh yes, you are in a tough spot there. The easy way to fix that would be to hook up to your mac, move all the files off the Mac partition, and start from scratch.
However, FAT32 has a max file size of 8GB, which is about 20 minutes of video at DV-AVI NTFS standard. However, I don't know if Mac writes to NTFS. It may now with it's latest 10.4, but it didn't back in the early days of OS 10.

If thats the case, the fastest way to transfer very large files would be network your mac and PC together. I have done that and it's not that hard with OS 10.3 or higher and Windows XP.

Gotta love cross platform work.

I found this on Ubuntu's forum, but I don't know if it will solve your problems.
HOWTO: Resize your HFS+ partition for free - Ubuntu Forums.

OSX can read NTFS but it cannot write to it (I work with Macs everyday, I've tried )

How shall I go about networking my computers through my Apple Airport Extreme?