Last fall I got an AVRISPMKII to program some ATMEGA168 chips. The programming speed seemed OK back then. But my programs have been steadily growing up in size and soon I had to painfully watch a 4 min progress bar to program only 16kBytes of Flash!
It appears the transfer clock speed can be adjusted and mine was simply too slow. You have to enter the terminal mode of the AVRISPMKII, check the current sck value with parms then you can change it if the value is too high. I used the proposed 10μs value and my transfer time immediately decreased to about 3-4s!
Note: despite the patch I described in Patching avrdude for OS X Tiger, it still happen that avrdude is unable to communicate with the programmer. Unplugging and plugging it again temporarily solves the problem.