Ok... about labeling Linux partitions, i can assure it works at least on Ubuntu installed to MBR scheme, on ext4 file system.
About multibooting OS X with Windows and Linux on the mix on a GPT scheme, for me it's asking for troubles like the one you just faced; neither Windows or Linux are prepared to live on GPT and it's pretty easy to get the partition tables out of sync.
Now, about renaming partitions, this
<key>Rename Partition</key>
<string>hd(0,3) Ubuntu</string>
should work, though i never tried it on a volume without label.
This
<key>Rename Partition</key>
<string>Ubunto UbuntuX</string>
works for me and this
<key>Rename Partition</key>
<string>"Mac OS X Install DVD" "OS X Install";Ubuntu "Ubuntu X"</string>
and this is how you handle it, when using labels with spaces and renaming multiple volumes.
Hope it helps