Pro Mini atmega168 voltage woes
Bypass the regulator, and connect the battery directly to the VCC pin. However, running at 16Mhz requires at least 3.8 Volts, according to the datasheet. Lower voltages may work, but aren't guarantied.