You can run the ATmega168P/328P down to 2.7V if you lower the clock frequency
to 10MHz. Check the Maximum Frequency vs Supply Voltage graphs in the datasheet.
Be careful when choosing a linear regulator for use in your battery system.
When your input voltage (Vin) is less than the sum of your output voltage (Vout)
and the dropout voltage (Vdo) then your linear regulator is not running in a linear
mode -- it is a saturated switch and will not regulate.
For 2AAs I would use a boost converter (either to 3.3V or 5V).
For 3AAs I would probably use an LDO (with a Vdo of few hundred mV's) to
get 3.3V and use a 12MHz XTAL.
(* jcl *)
www: http://www.wiblocks.com
twitter: http://twitter.com/wiblocks
blog: http://luciani.org