[shorod]

I would next remove the battery cables from the battery and thoroughly clean the terminals and the cables. Inspect the cables for corrosion. If you have the temporary bolt-on ends, remove them and inspect for corrosion. Throw them away at your first opportunity and replace them with proper cables. Inspect where the cables terminate for corrosion.

With the connections clean, reattach to the battery, making sure you have a good snug connection. Try to start the car again. Anything seem different? If not, have the battery load tested. You don't know how long the "new" battery has been sitting on the shelf. Sulfate can build up on the plates of the battery sitting on a shelf, reducing its storage capacity.

If all those prove fine, I would next suspect the starter motor. As the brushes in the motor wear down with use, they get to a point where the tension springs don't force them to make a good connection with the commutator and that's why you get the click, the solenoid is engaging but the starter motor isn't turning. Tapping on the starter motor housing jostles the brushes enough that that make contact with the commutator and the starter runs for another start or two.

-Rod