I recommend using the regulator I use on my Axon: L4940V5
It's rated for 1.5A and has reverse polarity protection built in.
As such, you can remove the polarity protection diode. Its the little black two pin chip right above the two cylinder shaped capacitors:
http://arduino.cc/en/uploads/Main/ArduinoDuemilanove.jpgJust search the part number to verify its a diode on the Arduino. After removal, short the two pins with lots of solder.
Now you can use a 6V battery to power your Arduino.
Now if you wanted to use a 3.3V battery you can use a 3.3V regulator, however most don't have built in reverse polarity protection so you'd still need the diode. Also, you'd have to replace the crystal with one for ~11MHz.
If its as easy as changing the regulator why didn't the manufacturer do it?
The Arduino is designed to be ultra cheap by sacrificing quality and features.
My Axon is the opposite, I packed it with quality and features, at the cost of a higher price.