Do you have the 20 MHz version of the part, and is your VCC within tolerance?
It's possible that the chip has the serial programming disabled, did you try another chip?
Beware, a virgin chip will be running on internal 1 MHz RC oscillator until you tell it otherwise, so setting your ISP clock to <250kHz is a good idea.