Few things to also check. 12Mhz+ only works on devices that run > 4Volts (ish). Make sure you're powering our device from above 4volts.
Also, new avr's have fuses set to use internal oscillator that runs after the ckdiv fuse at 1Mhz. Thus your programmer must be lower than 400kHz when doing the first fuse read. I would typically recommend about 128kHz until you set the fuses to use the external oscillator. Also if you set it to use the external oscillator and the crystal doesn't work, you have to wait till your crystal works before you will be able to use the chip again.
Finally what Xenoamor said, check your device for what one you have exactly. What is the signature you read out? Is it all 0's or F's or...?