Do the voltage test during cranking, and I'll bet you either have an under-capacity battery for the demand, or a bad battery. Just because the battery is new, or in good condition, doesn't necessarily mean it has the current delivery capacity to handle a starting load. If you're below 4.5 volts or so under starting load, you need more battery.
Jerry