I can replicate your error if I use a USBAsp programmer, and a fresh Attiny85
It is possible because i have not updated the firmware like described in this threadhttp://arduino.cc/forum/index.php/topic,149668.0.html
If I set the fuses to 8MHZ, it works.
Furthermore you could check the avrdude version
When I use Arduino IDE it uses version 5.11, and if I use the command line version 5.10 is used.
So maybe you have different versions too, that you use without knowing.