I tried speeds as low as 64K, still no joy. Also, note, I couldn't get AVRSTUDIO to even read the chips signature. My understanding is that this operation is designed to work even if the clock speed on the chip is only 32kHz.
My best guess is that there is a connection issue, either with my soldering (most likely), or with the circuit board (least likely).