I've used the exact same instructions to program an Attiny45 using an Uno with no problems. I am running my Attiny at 1Mhz which I believe is the default.
Maybe you should try 1Mhz just to see if that works. If so it would suggest the fuses are not being set properly for 8Mhz - but I'm afraid I have no idea why or what to do.
...R