Do you have an other programmer ?
If you use a cheap USBasp programmer, you need a cable from 10-pin to 6-pin.
What if you try to let Arduino to programma the bootloader again, this will also set the fuses.
But in the end, it is probably broken....
I don't have another programmer, but the one I have is working just great with other chips and boards I have. I have asked Arduino and avr-dude personally to try again, and it fails always on fuse verification, just like AVRStudio. I've also tried AVRStudio 4 as well.
Have you tried a "chip erase"?
Have you inadvertently set lock-bit LB2?
I have tried "chip erase", several times. I've also double checked the lock bits, they are all three set to "unlock" according to AVR Studio.
I'm guessing I did something to fry the '328. I'll just order up a new one and go from there.