Try adding this to your Arduino IDE preference.txt:
upload.verbose=true
This will turn on the debugging messages in avrdude. From that you should be able to see what signature is being read. You should also be able to tell what part of memory is not verifying.
When I got an error like this it was because I was using ArduinoISP without disabling auto-reset. Avrdude was talking to the Arduino bootloader which responds to the STK500v1 "Write lock byte" command by saying "OK" but when you read the "lock byte" back it always returns 0x00. If you are using a USBtiny (or equivalent) this should not be your problem.
Try doing the upload without the ISP programmer connected to the target board. If you get the same results It's probably a problem in the programmer.