The 12MHz crystal is probably for the USB chip. There should be a second crystal (or a tiny resonator) connected to the AVR.
There's a "compatible" chip to the M328 called the lgt8f328, that has some "improvements" like a 32MHz internal oscillator, DACs, 12bit ADC, and some other features. Perhaps you have one of those, that is incorrectly set up. (32MHz with div8 fuse would give you 4MHz?)
They apparently use a different programming technique than real AVRs, so fixing the fuses might be tough.