Are you dealing with the ATmega328 or the ATmega328p (the latter is more common, but sometimes people order the former from a parts supplier by mistake). The difference between the chips is that the 328p has support for Atmel's picoPower power-saving features. ...and to make things even more confusing, a lot of people talk about the ATmega328--or simply "the 328"--when they are referring to the ATmega328p!
I second MikeHg's advice to try programming in a development board such as the Arduino Uno. A development board can sometimes work when ISP fails for the clock itself--especially when the ATmega328's fuses (or ATmega328p's fuses) are set to rely upon an external oscillator.
By the way, I wrote the xmas firmware mentioned by MikeHg, and it uses the picoPower features to increase clock battery life. So if you are really using the 328 and not the 328p, the sleep functionality might not work properly with my firmware.
Here is a good thread on porting firmware to the 328p and it also applies to the 328:
http://forums.adafruit.com/viewtopic.php?p=164574 (It isn't firmware specific.)