I don't specifically know much about Solaris other than that it is Sun's Unix-flavoured OS. As such it is probably setup similar to Linux distros.
A simplified boot sequence is:-
(1) MBR (2) Active Partition's Boot Sector (3) OS Boot File
or if the MBR has been overlaid
(1) Grub etc on MBR (2) HDD sector chosen by GRUB etc (3) OS Boot File.
After you install W2K3 the first option finds ntldr on partition(1).
After you add FC3 GRUB is installed onto either the MBR or onto the boot partition depending on what choice you made. If the boot partition is a primary partition (as in this case) this then gets marked as active. In the process the setup detects the earlier W2K3 installation and by default adds an entry which points back to the W2K3 partition boot sector which in turn finds ntldr. If the boot partition is a logical partition a third party boot manager (whether that is GRUB, LILO, XOSL or BiNG) must overlay the mbr in order to point to the logical partition.
After you add Solaris a similar process to installing the Linux distro must take place but I dont know for sure whether or not there is an option to overlay the mbr or not. As with the Linux setup the Solaris setup reads what is already installed and adds the W2K3 and FC3 items to its own boot menu.
After you reinstalled W2K3 not only did you format the partition but the mbr would have been reinstated and partition(1) marked as active and any Solaris overlay on it would have been obliterated. Since all four partition tables were in existence the reinstated partition table entry should still be in the same place and thus not an issue; (this can be a very confusing issue with Linux in the way it enumerates, as opposed to mounts, partitions.
When you reinstated GRUB was this to the mbr or to the boot partition. In either case any Solaris overlay on the MBR would be non-existent and not capable of being even backed up. My guess is that is why you cannot now load Solaris and are going to need to either reinstall or repair it.
With such multibooting scenarios it is wise to make a backup of Track-0 prior to any manouvres (repairs, reinstallations, etc) and then if the setup has gone sour afterwards you can replace the original Track-0 and get back to the earlier boot set up.