I've finally got a solution to my problem (which I'm hoping is the solution to your problem as well
If you've already tried the following, I apologize, but this is what worked for me...
When I ordered the chips from Digikey, they came with the fuses set in the atmel default configuration which is DIFFERENT than what is set on the Arduinos (by default they are set to use the internal osc. instead of the external crystal on the arduino, they don't have the bootrst set, no brownout, etc).
So, when avrdude tries to read the device signature, the default 500kHz bitrate is too high, so you get back a garbage signature (sometimes it gets lucky and it read correctly, but mostly it was just garbage)
You have to lower the mkII's ISP freq to a speed supported by the default chips, fix the fuse settings, and then crank the speed back up on the mkII. Once you do that the chips work fine with the Arduino environment. I've been programming them all afternoon without hitch.
Here's the steps:
(FYI, I'm using AVR studio on Windows XP with a AVRISP mkII and an Arduino Diecimila powered via a wall wart)
1. Open AVR studio and go to Tools->Program AVR-Connect
2. Select your programmer and hit connect
3. Under the "Main" tab, click the Settings box (under Programming Mode and Target Settings)
4. Change the ISP Freq: to the lowest possible (51.1 Hz). Click Write to write the new ISP freq setting to the mkII, and then Read to double check that it wrote correctly. Then click close.
5. Click the "Fuses" tab and make sure that they are exactly like below (I got these from reading the fuse settings on a working arduino):
BOOTSZ - Boot Flash size=1024 words start address=$1C00
DWEN - uncheck
SPIEN - (this is checked with a question mark, I can't check or uncheck this, just leave it as is)
WDTON - uncheck
EESAVE - uncheck
BODLEVEL - Brown-out detection at VCC=2.7V
CKDIV - uncheck
CKOUT - uncheck
SUT_CKSEL - Ext. Crystal Osc. 8.0- MHz; Start-up time PWRDWN/RESET: 16K CK/14 CK + 65ms (this was at the very bottom of the list)
EXTENDED - 0xF8
HIGH - 0xDD
Low - 0xFF
6. Click Program to write the fuse settings. You should see the status box say OK! after writing and verifying the fuse settings.
7. Go back to the main tab and change the ISP freq back up to 500kHz.
8. Go to program, choose your bootloader, and it should program just fine!
9. Open the Arduino environment and test it out to make sure it works. You're done!