Clean both battery terminals and the ground end of the negative where it attaches to the frame or engine. I keep one of these little tools around that has wire brushes for cleaning male and female terminals. After using that I use a paste of baking soda and water and an old tooth brush. Then smear some vasoline on the terminals after everything is cleaned and reconnected. I've started more than one vehicle over the years that had the same problem you have after cleaning the terminals.
HTH
Pete
HTH
Pete