What I've been doing is programming fuses, programming lockbits, then programming memory.
Interface settings: 125 KHz for first time bootloading (Atmel AVR ISP MKii allows you to select the programming speed)
Memories:
C:\Arduino-1.0\hardware\mighty-1284p\bootloaders\optiboot\optiboot_atmega1284p.hex
Erase before programming- checked
Verify after programmimg - checked
Fuses:
BODLEVEL 2.7V (or as you select)
SPIEN - check
BOOTSZ - 512W_FE00
BOOTRST - check
SUT_CKSEL - EXTX0SC_8MHZ_xx_16KCK_65MS
Fuse Register
Extended - 0xFD
High - 0xDE
Low - 0xFF
Lock Bits: all show No Lock, Lock Bit Register to show 0xFF