I was bitten once by changing the clock fuses where it was not operating fast enough for the setting I was using on the programmer. The programmer would fail to communicate with the device.
The clock for the programmer must be no faster than 1/4 of the CPU clock.
I'm using Avrdude and there is a command argument to set the clocking speed.
For example:
avrdude -v -p attiny84 -c avrisp2 -U flash:w:main.hex:i -B 128
The -B argument specifies the clock period in microseconds.
This is assuming, of course, that you haven't accidentally programmed one of the other fuses that disables the ISP interface.
In that case a HV programmer may be the only solution. There are some simple designs on the web (can't find them at the moment) using an Arduino and a few other components to 'unbrick' mis-programmed devices. They can easily be built in can hour or so.