I have had this same issue today - compiling for ATtiny85 using Arduino Tiny 0015 and Arduino 1.0.3. It appears to relate to compiled sketch size - any arbitrary deletion from my code would make it compile but a few bytes bigger and it won't. Cut-off was around 4K.
Down-grading to 0022 or 1.0 did not help.
Down-grading to Arduino Tiny 0012 did not help either.
However, up- (or down- or sideways-, I'm not sure) grading to WinAVR20120110 from here: http://sourceforge.net/projects/winavr/files/
seems to have fixed it.
If you need assistance with the process, this is a very useful thread:http://arduino.cc/forum/index.php/topic,37965.msg281176.html#msg281176