Problem with programming an ATtiny85: Error - avrdude: Yikes! Invalid device signature
Try connecting the RESET pin of the Attiny85 to GND the second before you hit "program". 

In my experience, the Arduino does not always send the RESET signal when it should (or on the pin that you think it would send it). 

In these cases, manually resetting the Attiny by connecting the RESET pin to ground makes it programmable.

You can keep RESET low during the whole programming process, but if you keep it low for many minutes before programming the chip, it might not always work. In those cases, set RESET high for a moment before setting it back low, and the Attiny should be good for another round of programming.

And of course, when you want the Attiny to start doing what you have programmed it to do, you have to pull RESET high again.