I've done a little more research and verified the burned bootloader with the AVR Studio and AVR Dragon. It turns out that the bootloader does get burned correctly. My procedure was to first erase the entire Atmega1280 chip, then burn the bootloader with the USBtinyISP and Arduino-0017. This gave me (again) the error I reported in my previous post.
Afterwards, I verified the bootloader with AVR Studio and the AVR Dragon ISP. Here's the result:
OK
Reading FLASH input file.. OK
Setting device parameters.. OK!
Entering programming mode.. OK!
Reading FLASH .. OK!
FLASH contents is equal to file.. OK
Leaving programming mode.. OK!
So it turns out the Arduino-0017 programming environment reports a verification error, but the bootloader is in fact burnt correctly. There could thus be either a bug in Arduino-0017 or a bug in the AVRtinyISP...