I'm trying to fire up my version of AVR Studio5.1 to check - it doesn't seem to want to recognize my MKii since I changed the drivers for it to work with the IDE. Downloading 6.0 to see if that fixes it.
Sounds about right tho. Fuses look to agree with the settings in boards.txt:
mega2560.name=Arduino Mega 2560 or Mega ADK
mega2560.upload.protocol=wiring
mega2560.upload.maximum_size=258048
mega2560.upload.speed=115200
mega2560.bootloader.low_fuses=0xFF
mega2560.bootloader.high_fuses=0xD8
mega2560.bootloader.extended_fuses=0xFD
mega2560.bootloader.path=stk500v2
mega2560.bootloader.file=stk500boot_v2_mega2560.hex
mega2560.bootloader.unlock_bits=0x3F
mega2560.bootloader.lock_bits=0x0F
mega2560.build.mcu=atmega2560
mega2560.build.f_cpu=16000000L
mega2560.build.core=arduino
mega2560.build.variant=mega
That's why I do this in the IDE:
Burn the bootloader, which sets the fuses
Download the sketch via File: Upload Using Programmer, wipes out the bootloader, leaves the fuses, and the sketch starts immediately after a reset.