remove new battery. first, try cleaning (to bright metal) battery terminals and also other start circuit connection points to eliminate any voltage drops due to corrosion.
Also have your new battery LOAD tested by a competent shop. Those batteries - even new - are notorious for being faulty as purchased.
post back with update if prob still continues...