How about some more specs on the computer: make, model, BIOS version/revision.
Info about the make, model, capacity and the partition table geometry of the UFD. I've seen some where I attempted to redo the geometry but it stopped booting some machines.
Tried running a SYSLINUX installer (syslinux or extlinux) against it manually? Checked for a valid MBR?