All IntelMacs have the ability to boot from USB, but to date I have only ever installed OS X to USB drives and booted off of them. So unfortunately for you, I have no advice to give.
But, lets asked some questions.
Does the drive work on any other system?
The drive is brand new. Works on Windows and the Mac.
Were the instructions supposed to be good for any system?
The instructions were strictly for Mac. I'm looking for it atm, but can't find it. It was somewhere in the official Ubuntu documentation.
What OS did you use to format the USB stick?
First attempt was in Windows using a third party USB installer: http://www.pendrivelinux.com/create-a-ubuntu-9-10-live-usb-in-windows/
After that failed, I tried the instructions from the Ubuntu docs for installing it to the USB drive with the Mac.
What partition table type did you use if you formatted from OS X (GUID, APT or MBR)?
Didn't partition or format the drive at all. This might be the problem and will try it once I get back home.
Do you like bunnies?
Depends on their color.