I've also tried using the Arduino as ISP method, but it's a bit unclear whether this is supposed to be able to burn the Mega 2560 bootloader.
In any case, any attempt to upload a sketch fails like this ("Upload Using Programmer" with Programmer set to "Arduino as ISP", and the ArduinoISP Example sketch running on the Duemilanove):
avrdude: stk500_getsync() attempt 1 of 10: not in sync: resp=0x15
avrdude: stk500_getsync() attempt 2 of 10: not in sync: resp=0x15
avrdude: stk500_getparm(): (a) protocol error, expect=0x14, resp=0x14
avrdude: stk500_getparm(): (a) protocol error, expect=0x14, resp=0x01
avrdude: stk500_initialize(): (a) protocol error, expect=0x14, resp=0x10
avrdude: initialization failed, rc=-1
Double check connections and try again, or use -F to override
this check.
avrdude: stk500_disable(): unknown response=0x12
the selected serial port avrdude: stk500_disable(): unknown response=0x12
does not exist or your board is not connected
Trying to "Burn bootloader" produces the same result.