Figured I'd post some kind of follow up here for others that might be having the same problem.
Turns out I was being too clever for my own good. The ATmega128 has an ISP pinout that doesn't match any other AVR I've ever worked with.
The MOSI and MISO pins on the SPI unit are not used for serial programming. The TDO and TDI pins are.
After figuring that out, I was able to get a response from the m128, but I hit some other snags with the bootloader.
The scripts that come packaged with the bootloader seem somewhat broken. There are absolute paths that require editing to resolve and I couldn't run the bootloader id patch script in windows with just Perl installed, so I ended up doing it on a linux machine. Cygwin would probably work though.
After patching and flashing the bootloader and flashing the fuse bits, I wasn't able to get a response from VemsTune.
I ended up stitching the firmware and bootloader hex files together in a text editor by removing the last line of the firmware's hex file and pasting the bootloader lines in after it. After flashing, everything seems ok.
VemsTune can talk to the box and the serial number shows up properly.