I had this problem recently. I'm quoting the vendor of my motor controller here:
What's most likely happening here is, a command with 4 motors to go straight from 0% to 100% causes a gigantic current spike, which drops the voltage of your battery for a short time. If it drops below the voltage at which the motor driver can function, that will shut down momentarily. When the spike is over (i.e. when the shutdown causes the motors to no longer draw current), the system will restart.
There are really two solutions to this. The first is to get a bigger or higher-voltage battery; the more room it has to play with in voltage and current, the less likely it is to brown out when that command is given. The other is to make your speed transitions a little more gradual. An R/C or analog input, even with hard acceleration, has a certain degree of ramping up. A serial input makes that change instantaneously.
The speed controller ceases to function at around 5.5V. It isn't in the user guide, since it crops up very rarely.
What happens is that batteries have a certain degree of internal resistance, so the more current being pulled out of them, the less voltage they supply (I=V/R). Since the internal resistance is usually pretty small, it doesn't come up during normal use. In a big spike, though, the voltage drops to a fraction of what it would be, and there's also a threshold for most batteries where it drops off even more. This voltage not being high enough to power your components causes a brown-out.
A bigger battery will generally have a lower internal resistance, and a higher-voltage set of batteries has more V that it can acceptably lose. More gradual throttle commands will decrease the height of the spike, so both your solutions should work. I would caution against putting more than 24V into the 2x10, though. =)
I tested these solutions and using a higher battery voltage solved the problem. I have my batteries in series now instead of parallel. This boosted the voltage from 12 to 24 Volts.
I also don't use full-speed commands initially. I use slower speed motor commands to start off and then later ramp up to faster speeds. So having a higher voltage and drawing less current initially reduces brownout. That is the technical word the technician used.
edit:
Keep in mind that my speed controller is from a different vendor (i.e. not Parallax). The same principal applies probably to your speed controller, though the maximum and minimum voltage to the Parallax may differ from mine.