I ordered 16 NiMH cells from Amazon along with a charger. I also found a battery holder that accommodates 8 AA sixed cells and replaced the holder that was supplied with the kit. So far, the NiMHs seem to have done the trick in being able to supply the peak current needed for the motors.
As an aside, the iPad bluetooth control app seems to be far superior to the Android version and even more robust than the version that runs on the iPhone.
The Makeblock team replaced a 25mm motor very promptly. Now it's time to have some serious fun with it!