CrossRoads:
Try a regulator like this
http://www.pololu.com/catalog/product/2110
6V in, 5V out, efficient.
sorry to bring up this topic, but based on this recommendation...
how would you connect the 5Vout to the arduino?
I am reading threads like this one and i am a bit confused on the best way to power the arduino