"out of sync" error flashing bootloader to Arduino Mega 2560

I started getting verification errors when trying to download code to my Arduino Mega 2560, so I'm attempting to reflash the bootloader using a spare Arduino Duemilanove as a programmer. I was able to successfully set the fuse bits, but when I attempt to actually upload the hex file, I get an error:

avrdude: stk500_paged_write(): (a) protocol error, expect=0x14, resp=0x11
avrdude: stk500_cmd(): programmer is out of sync

This is the command I am running along with the output:

> /usr/share/arduino/hardware/arduino/bootloaders$ avrdude -P /dev/ttyUSB0 -b 19200 -c avrisp -p atmega2560 -e -v -U flash:w:stk500v2/stk500boot_v2_mega2560.hex -U lock:w:0x0f:m

avrdude: Version 5.11.1, compiled on Oct 30 2011 at 10:41:10
         Copyright (c) 2000-2005 Brian Dean, http://www.bdmicro.com/
         Copyright (c) 2007-2009 Joerg Wunsch

         System wide configuration file is "/etc/avrdude.conf"
         User configuration file is "/home/thomas/.avrduderc"
         User configuration file does not exist or is not a regular file, skipping

         Using Port                    : /dev/ttyUSB0
         Using Programmer              : avrisp
         Overriding Baud Rate          : 19200
         AVR Part                      : ATMEGA2560
         Chip Erase delay              : 9000 us
         PAGEL                         : PD7
         BS2                           : PA0
         RESET disposition             : dedicated
         RETRY pulse                   : SCK
         serial program mode           : yes
         parallel program mode         : yes
         Timeout                       : 200
         StabDelay                     : 100
         CmdexeDelay                   : 25
         SyncLoops                     : 32
         ByteDelay                     : 0
         PollIndex                     : 3
         PollValue                     : 0x53
         Memory Detail                 :

                                  Block Poll               Page                       Polled
           Memory Type Mode Delay Size  Indx Paged  Size   Size #Pages MinW  MaxW   ReadBack
           ----------- ---- ----- ----- ---- ------ ------ ---- ------ ----- ----- ---------
           eeprom        65    10     8    0 no       4096    8      0  9000  9000 0x00 0x00
           flash         65    10   256    0 yes    262144  256   1024  4500  4500 0x00 0x00
           lfuse          0     0     0    0 no          1    0      0  9000  9000 0x00 0x00
           hfuse          0     0     0    0 no          1    0      0  9000  9000 0x00 0x00
           efuse          0     0     0    0 no          1    0      0  9000  9000 0x00 0x00
           lock           0     0     0    0 no          1    0      0  9000  9000 0x00 0x00
           calibration    0     0     0    0 no          1    0      0     0     0 0x00 0x00
           signature      0     0     0    0 no          3    0      0     0     0 0x00 0x00

         Programmer Type : STK500
         Description     : Atmel AVR ISP
         Hardware Version: 2
         Firmware Version: 1.18
         Topcard         : Unknown
         Vtarget         : 0.0 V
         Varef           : 0.0 V
         Oscillator      : Off
         SCK period      : 0.1 us

avrdude: AVR device initialized and ready to accept instructions

Reading | ################################################## | 100% 0.06s

avrdude: Device signature = 0x1e9801
avrdude: safemode: lfuse reads as FF
avrdude: safemode: hfuse reads as D8
avrdude: safemode: efuse reads as FD
avrdude: erasing chip
avrdude: reading input file "stk500v2/stk500boot_v2_mega2560.hex"
avrdude: input file stk500v2/stk500boot_v2_mega2560.hex auto detected as Intel Hex
avrdude: writing flash (262106 bytes):

Writing | ################################################   | 96% 0.00s
avrdude: stk500_paged_write(): (a) protocol error, expect=0x14, resp=0x11
avrdude: stk500_cmd(): programmer is out of sync

Any suggestions?

Thanks!