Recommendations for Arduino bot power source?

Okay, I posted more or less the exact same post over at the Sparkfun forums, and then I thought I should post it in the the Arduino forums to elicit as much feed back as possible. I accidentally posted it in the section for interfacing with software and didn't get any replies. Hopefully it is more appropriate here and some folks might have some advice for me.

I'm working on my first robot project. It's a sort of mishmash of some tech stuff that caught my eye.

I started down this road with my interest in learning electronics by working with the Arduino Diecimila. Since that time I have acquired a Nokia N800 Internet Tablet.

I decided I wanted to rig up a simple DIY remote controlled vehicle using Nokia to send commands to the Arduino via Bluetooth. For this purpose I purchased Sparkfun's Blue SMiRF (Silver), a Tamiya Dual Gearbox, and an H-bridge chip.

I've had a lot of fun learning how to put all this together. For the truly curious, check out this post in this thread for a description of what I was trying to accomplish. This post describes what I did up to the point of switching from the hard wired serial cable to the BT connection.

In fact switching from the cable to BT was one of the least complicated aspects of the project. Now I have the first version of my BT vehicle up and running.

My problem is that I currently have two different power supplies: a 9v batter powering the Arduino and a 2AA pack powering the motors. There are a couple of issues with this. First, it is inconvenient to fix the two battery units to the vehicle. Second, the Blue SMiRF seems to draw a lot of power out of the 9V. As I was finalizing the first prototype today, I drained the 9V down to barely more than 7 volts (as indicated by my cheap Radio Shack multimeter). This was below the threshold to power my Blue SMiRF.

So I would like to find a single power supply solution that I can use to replace both the 9V and the 2AA packs. Obviously I would like it to hold the charge for as long as possible. And being rechargeable would be a bonus too. Ideally, the prefect power supply would provide three separate supplies: one for the Arduino and associated Blue SMiRF, and two addition supplies for the two motor controls of the H-bridge.

Does anyone have any suggestions?

You could replace the 9V batt with something like this:

You would connect it to the +5V pin on the Arduino rather than the barrel jack.
It can supply ~ 300ma.
The power to the converter would come from the same pack you are using.
(You could put other 2xAA packs in parallel for longer run time.)