After picking up a few blank ATMega328P I was ready to upload the Arduino bootloader with the latest Olimex AVR-ISP500 USB STK500v2, but ran into a few issues. Here's how it finally came together and worked: First, if programming with the chip in place in an Arudino Duemilanove, make sure the board has external DC power. Next, if burning through the Arduino IDE, amend the following sections to ../hardware/arduino/programmers.txt and ../hardware/arduino/board.txt. Finally, after restarting the IDE, make sure to select the newly added board, the correct serial (e.g. /dev/ttyACM0), and click on the newly added bootloader burn option. When failing, it took only a few seconds to give up, while the successful burn took about two minutes. Thanks to the unknown poster on the Sparkfun product page for these snippets.

programmers.txt
olimexisp.name=AVR ISP 500 Olimex
olimexisp.communication=serial
olimexisp.protocol=stk500v2

boards.txt
##############################################################
avr500atmega328.name=AVR500v2 programmer with ATmega328
avr500atmega328.upload.using=olimexisp
avr500atmega328.bootloader.low_fuses=0xFF
avr500atmega328.bootloader.high_fuses=0xDA
avr500atmega328.bootloader.extended_fuses=0x05
avr500atmega328.bootloader.path=atmega
avr500atmega328.bootloader.file=ATmegaBOOT_168_atmega328.hex
avr500atmega328.bootloader.unlock_bits=0x3F
avr500atmega328.bootloader.lock_bits=0x3F
avr500atmega328.build.mcu=atmega328p
avr500atmega328.build.f_cpu=16000000L
avr500atmega328.build.core=arduino
##############################################################