Sorry for late reply. I tried with both SLOW_SCK on and off. But the Duemilanove bootloader never worked. I even tried the chip by putting it on a firend's Arduino NG board instead of bredboard. But it doesn't matter now, I am using the chips fine with optiboot recompiled with baudrate set to 57600bps. I'll be getting some better crystals next week, hope that will solve everything.
I would've posted a picture of the setup, but believe me or not, I don't even have a working camera for that. :~