If you've got a multi-meter or other battery tester it wouldn't hurt to look for a voltage drop in one of the batteries. It's unlikely since they're new, but entirely possible. Where it grounds onto the frame is a common place to get a partial connection. This all ties in with Docsgsxr's diagnosis. It's a lack of power getting to the starter, or the starter itself. Bad batteries, bad ground or bad starter. I would make sure the ground is cleaned and reattached metal on metal so it's good for another 20 years.