If they came from RS, then I would not expect them to be bad, have you tried slowing down your programmer bitclock in case the tiny is running slower than expected, -B<number> option to avrdude (I forget what numbers are valid, 1-10 higher slower I think), provided your programmer supports it.
You could try injecting a square wave of say 8MHz (into CLKI), just in case it's fuse is set to require external xtal/clock.