Have you still got the OSX install disks? When you start the installation, you can go to the Disk Utility (it's on the menu bar). You could format the drive as a HFS+ partition and as far as I know mark it bootable. (I might be wrong on that last bit).
However, when it comes to installing linux, as far as I know you'll have to update to at least Fedora 6, because that was the first release with GPT compatibilty. I've installed FC6 and F7 on my MacBook Pro using the same method each time. Here goes.
You must have Mac OSX on the first and second partitions to get a GPT table. The first one is a boot partition. After you've installed OSX and updated firmware etc., install Bootcamp and shrink the OSX partition and create 2 new ones, one for XP, one for Fedora. Install XP. Also install rEFIt (
http://refit.sourceforge.net/) which is a bootloader for intel macs.
When it come to installing Linux, this is where I had problems. The Disk Utility will force you to create a partition with some sort of file system (I used DOS, FAT32). However, when it came to partioning with disk druid I was told there wasn't enough free space and you're supposed to do a default partioning setup (not custom). So I exited the install, and used a Knoppix live CD to delete the partion OSX had created. Then re-did the install and chose 'Use free space for default setup'. Also make sure you install grub on the Linux partition, not the MBR.
After completing the installation, reboot and when the rEFIt screen comes up use the arrows to pick out the Partioning Tool and use that to sort out your MBR table. Otherwise, you won't be able to see the Linux drive. Even after that, when you do see a second or third hard drive in the menu, when you chose it you'll get Missing Operating System instead of Grub.
The cure for this is to reboot using the Fedora CD and go into rescue mode. I had to use an external keyboard to move the arrows. After you've typed:
chroot /mnt/sysimage
then type
grub-install /dev/sda3 (or whatever the linux partition number is, just make sure you get that right!)
After that, reboot and the next time you see the rEFIt menu, there'll be a Penguin right beside Windows XP!
I know that all seems very long-winded, but I completely re-built a brand new Mac 4 times in one week before I got that sorted. Hopefully it works for you.