@lwfitz -
Does your UEFI computer recognize the USB as a UEFI boot device? Our Toshiba does not, I believe, so booting from USB is whacked if it happens at all. Try burning a CD/DVD if you have one.
Also, is Windows installed on that computer? for some reason, I have to boot Windows, then reboot to get a CD to boot. That's something internal to Windows - in addition to the speed boot which needs to be disabled.
Verify your BIOS is set up correctly.