UPDATE 2
If the tiny is running a sketch then it must already have a bootloader.
I think there are a lot of factors to be wrong here because the tutorial was written pre arduino 1.0. I think the 1mhz one is a problem and best avoided for now. The tin85 w/ Arduino ISP sounds to be pre-arduino 1.0 and needs to compile correctly.
In a few days I will have some time so if you haven't fixed it by then I hope to give you some info.
First I will take 2 arduinos, one as ISP and one as normal arduino. We need to prove the ISP sketch is working correctly when uploading blink to a 2nd arduino.
Once the ISP is proven with arduino 1.0 we need to see why normal compile of the tiny85 fails. It might be there is an updated tiny85 hardware folder for arduino 1.0 on the web but if not then we can change the tiny85 hardware folder sources to use 1.0 instead (hopefully).
FYI: You mention the arduino.h, in versions earlier than arduino 1.0 the file was called wprogram.h, arduino 1.0 also expects a few other differences. If the tiny85 is including wprogram.h I think it will be a problem to also include arduino.h
IDEA
If you have some time spare why not go onto the arduino.cc and down load version 0023 of the arduino IDE. (All of the older version of arduino are available). Upload the Arduino ISP example to the UNO using 0023 then try the upload to the tiny85 (w/ arduino ISP) for the blink sketch. I would expect 0023 to work exactly like the video, so if it fails you can look to the wiring of the tiny85 for the problem. It it works we will know we need to update the tiny85 hardware folder to arduino 1.0 format
If it works in 0023 then you should follow Deans instructions above for Arduino 1.0.1.
UPDATE
The only way I can find to reproduce the error you see is if I attempt to "Upload using programmer" when the programmer is set to "AVRISP". If I upload the ISP sketch to an arduino and attempt to program an unconnected tinyxx I get different errors.
So sorry if these are time wasting questions but.. are you clicking "Upload" in the arduino ide or "Upload using programmer"? You should be clicking "Upload" after selecting the ATTiny (w/ Arduino ISP) as the board.
Info..
It is a bit confusing but the board definition for ATTiny xx (w/ Arduino ISP) forces the correct programmer settings for the normal arduino "Upload". In the arduino ide, the menu item "Upload using programmer" uses whichever programmer is selected on the "Tools>Programmer" menu, in this case probably AVRISP mkII which, if unconnected, will produce the error you have reported.
Best Answer
Section 19 of the ATtiny24/44/84 datasheet, "Memory Programming", subsection 5, "Serial Programming", gives the minimum pulse width for ISP. Based on the values given (a minimum of 3 clock pulses for high and low each for a system clock >= 12MHz) the ISP clock must be no higher than 2MHz. As long as you can find a programming algorithm that respects that (and most do), you can use it to program the device.