project not working when switching to battery power
You may find that, with a high load on batteries, it's depleting the battery quickly; batteries often recover after a while, which may be confusing things further. Try using a multimeter to measure the voltage on the battery, when your program is running.

The Arduino (actually, the chip that runs the Arduino) has brown-out detection - if the voltage drops below a certain level, the Arduino will shut down; if the power comes back up, the Arduino will start up again - but reset. The chip has settings for 1.8v, 2.7v, and 4.3v brownout detection (or none at all!); something I read on the interweb (if you can trust that) said the default was 4.3v. It may be worth flashing an led on startup, so you can tell when the chip is reset.

Also, if you are powering the Arduino through the voltage regulator (using the power socket on the Arduino), then you need about 6-7 volt in just to get 5 volt at the Arduino - this causes further power loss. If using 4 AA batteries through the voltage regulator, you will get 6 volts (probably a little more when the batteries are fresh) going into the regulator - barely or not quite enough! - and the voltage on the Arduino is likely to be below the 5v it needs. Any load (in one of my projects, two large 7-segment displays) can cause the voltage to drop enough to trigger a reset. If you are using the voltage regulator, check the voltage between the 5V and GND pins.