Atmega128A problem -- Using MegaCore

Did you select Tools > Programmer > Arduino as ISP when you tried to burn the bootloader? When I do that my avrdude command is different(-cstk500v1 instead of your -cstk500 which ends up specifying STK500V2).