Comment 6 for bug 293083

I think (in my case) the problem was the boot record on the USB stick. I used Puppy Linux to set itself up for booting off the same USB stick. This failed to boot with the same message "Invalid or corrupt boot sector".

In the Puppy Linux wizard, there's an option to replace the boot sector. Since the boot sector seemed to be at fault, I replaced it with the syslinux version (which Puppy Linux suggests works best). Puppy Linux booted, so I just retried with Ubuntu 8.10 - on the same stick, after deleting the Puppy files- which also worked.

It seems that the Ubuntu USB creation wizard doesn't touch the boot sector. Which is fine most of the time, but apparently not always:
http://www.pendrivelinux.com/install-a-new-mbr-to-your-usb-flash-device/.
Kingston USB drives are quite popular, the problem could be common.

A similiar option to replace the MBR, along with some advice about when to use it, in the Ubuntu USB-creator GUI could save other neophytes some headscratching...