What you don't say is what the accuracy of this internal oscillator is. It took me some time to find it in the datasheet, on page 369.
10%. Ten percent! And that for a calibrated oscillator? This is awful. It isn't unreasonable to expect error as low as 1% for this. Microchip/Atmel provides a document for calibrating the oscillator yourself to 1% accuracy.
I2C is a synchronous protocol, and timing accuracy isn't relevant as long as minimum and maximum pulse times are respected.
UART on the other hand is asynchronous, and then timing accuracy is important indeed. Most UARTs allow a half bit error in the last bit (the stop bit), so that's 5% for a 10 bit transmission.
The factory calibrated oscillator won't do here. You'll have to go through the calibration procedure to get to 1%. In that case you can use the internal oscillator. Otherwize you'll have to use a crystal.
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
You would need to add a new hardware configuration. Here the procedure is explained for an ATMega328: http://arduino.cc/en/Tutorial/ArduinoToBreadboard but you would need to adjust the example hardware config or maybe you'll find a working one.