The most common cause of a "locked" chip is to have set the fuses for something like "external oscillator" when you actually have an external crystal; since this shuts off the chip electronics that drive the crystal, there is no working clock, and ISP programming doesn't work without a clock.
You may be able to fix this by injecting a clock to the proper pin. Adafruit's ISP Programming Shield
is set up to do this, and you might get away with a simple temporarily-connected oscillator or 555 timer or something.
See http://www.avrfreaks.net/index.php?name ... c&t=106325
for more details.