Is the output from those 5 batteries in series going into the Arduino's external power input (barrel connector or GND/Vin pins)? That's the input of a linear voltage regulator that needs at least 6V, preferably a little bit more, to provide good 5V for the Arduino. NiMH batteries only have a nominal voltage of 1.2V, which adds up to 6V for the 5 of them. Granted, they run more like 1.4V when they're freshly charged, but then they drop down to 1.2V, and eventually down to 1.0V each. I wouldn't be surprised if the voltage from the battery pack is going too low to make the regulator happy long before the batteries are actually "dead".
Also: battery capacity figures are always calculated using the best possible conditions, so you should never be surprised if in the real world, mA * h is less than the rated mAh
