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.
This is not a very explicit error, I give you that. It could be lots of things, but I think I remember I had this particular error a while back because of bootloader issues.
The bootloader on most arduinos listens for a few seconds on the USART, checks and copies a code if it receives a correct one or otherwise just gives up, then calls the main program and does not run in the background. Therefore when the uploader tries to communicate with the board, it might be already running the main program and be unresponsive, hence the "not in sync". The simple fix is to hit "upload", wait for the program to compile, and reset the board just when the program starts being uploaded. There must be a second leeway, but it has always solved the problem.
I think I remember it's also possible to upload a code compiled for another board, which prevents proper synchronisation once the wrong code is uploaded. Not sure under which conditions this can happen (probably when the bootloader is uploaded and run together with the main program as one single program), but that would be worth investigating if none of that works.
Last resort, I'd buy a programmer (it's a good investment) and upload a fresh bootloader+blink program.
Either way, I'd look at the bootloader code of your platform online. Not only there might be the answer to your problem, but you'll also find the baudrate you're supposed to talk to the board with (19200 in the newest versions, it seems). If you never tempered with the bootloader, it should be the stock one.
Without external components connected to force short circuits on the outputs etc. it is virtually impossible to break a board by experience.
Best Answer
Have you ever programmed your ATmega328P successfully before? If not, that message most likely mean a configuration problem. It is just saying your IDE can't communicate with the MCU. It may take a while before you can successfuly program your ATmega for the first time. In this case, I can't help you without more information about your setup.
If you were able to program it at some point, but can't do it anymore, then the message you're getting from avrdude may be a sign that your MCU is no longer working.
To check if your ATmega is still alive, follow these instructions:
Does the ATmega still display its heartbeat? Normally the bootloader for Arduino Uno and similar boards have a heartbeat feature to tell the users it's alive: it's three quick blinks on the LED attached to pin 13, right after boot. Does yours still do it? If so, you can relax: it's alive.
If it does not blink three times anymore, has it ever blinked after boot before? For example, when you hooked up your Arduino board to a USB port in your computer (I'm assuming you have a USB board), has it ever blinked three times after boot?
I don't want to alarm you or anything. I'm not saying that your ATmega is burnt. But it is kind of difficult to really know when it is burnt. The message you're getting is one sign of it, but can be many other things. I have burned 3 of those chips, myself, and it is a sad moment, that's for sure.
In my case, a few things hinted at the problem. Before I had the problem, I was able to program my MCU using my Arduino Uno board. At some point, I did something that made the MCU stop working. Often is some short-circuit I caused when making changes to a circuit in a breadboard. After that event, the heartbeat stopped and I could no longer program the chip with my Arduino Uno nor burn a bootloader on it. The message from avrdude in all my cases were the same one you're getting. I could however program other ATmegas I had laying around using both methods (that meant it wasn't a problem with the board).
If your MCU continues to do the heartbeat, then it's alive and you are experiencing some other problem, probably communication or IDE configuration. What I usually try next is to burn the bootloader again. If the MCU is ok, it will happily take the bootloader. This way, you also make sure the right bootloader is in place.