I've got Ubuntu 13.10 (I tried 12.04 as well) installed on my usb (8GB Sony). I didn't do any partition, but set the Partition Map Scheme to Master Boot Record.

I want to boot this usb ubuntu on both Mac and PC. However, it doesn't always work!

------ working ------
My usb boots on PCs: I tested on two PCs, one with Win 7 and another with Win 8 installed.
My usb also boots on my Mac Air currently running 10.9 (upgraded from 10.7 to 10.8 to 10.9). This Air is 13-inch, Mid 2012.

------ not working ------
My usb does not boot on my Mac Pro currently running 10.8 (upgraded from 10.6 to 10.7 to 10.8). This Pro is 15-inch, Early 2011. This Pro does not show the usb option when I restart the computer while holding ALT key.
My usb does not boot on my iMac currently running 10.8 (not sure about the history). This iMac is 20-inch, Mid 2007

Other tries:
Change the Partition Map Scheme to GUID --- Windows won't boot my usb
More than one partition --- some boot, some won't

How can I make a usb with Ubuntu that boots on both PC and Mac? I'll also need two more other partitions, so Ubuntu sits on the first partition, some other data can be saved on the other partitions.

I don't want to install rEFIt on my users' computers, but I'd love to configure it on my usb if it helps.

Thanks in advance.