This page* says that Arduino 1.0.2 doesn't work with the ATtiny85, or at least not with some particular Arduino ATtiny interface drivers. Maybe that was fixed in 1.0.3 or doesn't relate to the Arduino software you're working with at all, but perhaps you need to back up to 1.0.1, like they suggest? Just an idea, I'm only using ATmega328's at the moment myself.
*
http://hlt.media.m i t.edu/?p=1695 - you'll have to remove the spaces in M I T yourself, since the spam filter apparently came from Harvard.