The ISP clock is dropped to 125 khz (and I've tried lower too). I tried it again, this time with the atmega328p from my arduino, and once again it failed. ispEnterProgMode: Error status received: Got 0xc0, expected 0x00, ModuleName: TCF (TCF command: Device:startSession failed.). This failed, giving me Failed to enter programming mode. I updated the devices firmware (to 1.16), and then tried to read the signature of the attiny85.
So I booted into Windows 8, installed Atmel Studio 6 and the drivers for the AVRISP mkii. I set all the /etc/udev rules correctly as far as I can tell, and still no dice. I tried using avrdude -c avrispmkii -p t85 -P usb -t to see if it was a problem with the Arduino IDE setup, but that gave me the same error. When I switched to using my Arduino as ISP, it programmed fine. I even tested multiple ATtinys so it's very unlikely that they're all duds.
I kept getting an error suggesting that it wasn't wired correctly, but I've checked it multiple times (and it's powered externally at 4.8v). I recently bought a dozen ATtiny85 MCUs and I was trying to test one simply by putting a blink program on it via the Arduino IDE with and AVRISP mkii (Arduino 1.0.5, Ubuntu 13.04).