AVR Atmega32 flash verification error
Have you been able to verify at all that the device is responding at any level?  You say you programmed the fuse bits, but have you been able to verify that they were actually changed?

According to the data sheet: 

The SPI Serial Programming instructions will not work if the communication is
out of synchronization. When in sync. the second byte ($53), will echo back
when issuing the third byte of the Programming Enable instruction. Whether
the echo is correct or not, all four bytes of the instruction must be
transmitted. If the $53 did not echo back, give RESET a positive pulse and
issue a new Programming Enable command.


Perhaps you could see if you can test this, either with an option to/modification of avrdude, or even just looking with a scope to see if the miso line is wiggling at all?

I'd think the question has aged enough that if it's still an issue, ordering any older chips from the atmega8/16/32 family to test the programmer would be worthwhile.  

The atmel literature seems to imply that the change are primarily fab process related, so it's possible that the new device might be more noise sensitive in some respects.