Just in case it saves anyone some trouble...
ISP is limited to about 1/4th the speed of the master clock of the AVR. If you have a blank, never before used AVR it's generally safe to set the ISP speed to ~125KHz for the first time you try to program the device and set the fuses. Note that if you set it higher you can get erroneous results talking to the AVR, or worst case flip some bits you don't want flipped and make it somewhat tricky to regain control of the AVR. (Most frequently this happens by setting the oscillator to a setting that is incompatible with the hardware you're using.)
Once the AVR has been programmed and the fuses set, it will be running from the 28.636MHz clock, so you can safely turn up the ISP frequency up to 4MHz. That speed lets you erase and reprogram the entire ATMega644 in just about 2.5 seconds. (Which is really nice if you're doing a lots of little experimental downloads!)
Also, on the AVR ISP MK2, you'll have two green lights if the USB connection is good and power is good on the target (Uzebox). If the light farthest away from the USB plug is red, power on the target is most likely off. If it's flashing orange you have the ISP cable on backwards. It's worth mentioning as well that if the ISP MK2 is attached but disconnected from the USB on the host computer it will in all likelyhood hold the AVR in reset (preventing any code from running).
-Clay