It could be that the brownout detector voltage set by the extended fuse byte is too high. You can check this by using avrdude to read the fuse bytes, and then using http://www.engbedded.com/fusecalc to decode them. Bear in mind that the brownout detector is referenced to the internal 1.1v reference, which has a tolerance of around +/-9%.
Can you confirm that you have at least one 100nF decoupling cap between and close to the Vcc and ground pins of the mcu? Also that you have connected Avcc to +5v and Agnd to ground even if you aren't using the ADC?