OK. I'm going to run down the connections that I have while I'm trying to program the ATTiny. Pin 1 of the ATTiny is ID'd by the small dot on the packaging.
Arduino ATTiny 85
Reset is connected to Ground with a 10uF capacitor
5v to Pin 8-ATtiny
GND to Pin 4-ATtiny
Pin 13 to Pin 7-ATtiny (SCK)
Pin 12 to Pin 6-ATtiny (MISO)
Pin 11 to Pin 5-ATtiny (MOSI)
Pin 10 to Pin 1-ATtiny (Reset)
Pin 9 to LED (Heartbeat)
Pin 8 to LED (Error)
Pin 7 to LED (Programming)
There are no other connections to the ATTiny (Two pins, 2 and 3 not connected). I checked that power is running to the VCC pin (Pin 8ATTiny) by using an LED. All of the above connections were just re-checked.
I have a spare ATMega328 and I'm willing to try burning that. It shipped with an Arduino Bootloader. I haven't played with that yet. I don't have the Hardware file for it. I'd try it myself, but I don't want to muddy the waters.
I do have the second Arduino Uno sitting here on my desk. I've tried that and gotten the same results.
I have a Dragon AVR programmer here as well. I couldn't get it to program the ATTiny either (I couldn't get it to read the Device ID of the ATTiny as well). I don't know if I could use that to troubleshoot or not.