I would think an arduino would not be a problem on a battery as long as there were no significant power spikes.
The datasheet says "absolute maximum voltage" is 6V. What happens if you stick 4 brand new, hot AA batteries that are a little over 1.5V each on there? Slip a few AA lithium cells in there - they are 1.7V new. It may not die immediately, but you will stress the ATmega and shorten it's life (again, from the datasheet).
Other microcontrollers (including the lower speed, lower voltage versions of the ATmega8/168, as used on the lillypad) can operate over a wider voltage range. Putting a nominal 3V battery (that you may get 3.2 V out of when it's new) on a part rated for 6V is no big deal.
Low voltages are bad, too. I used a 3 cell 4.5V battery to power my arduino and got very strange results when programming (no program uploaded, program was corrupt, even wiped out the bootloader once).
I think the FTDI rs232/usb chip has tighter tolerances (5.5V absolute max rating, IIRC).
Know the datasheet before you start changing the power supply.