Double check all of the connections; the battery terminals, ground straps, starter posts, etc. Make sure they are freshly cleaned and tight. Also test the charge level of tour new battery. Often they are left to sit on the shelf for very long periods and not kept charged, so they loose a lot by the time you get it. Also test the voltage at the starter (compared to at the battery) to be sure the cables are good. However it does sound like you have a starter solenoid/bendix issue, but it might be the connection; there is a wire that connects to the "bendix portion" from the "starter motor portion", a poor connection prevents the drive from engaging when the motor spins. The location of the starter allows lots of oil, grease, road grime, water to foul the connections.