Well, you can't rule out the possiblity the new battery has failed. How much corrosion was on the cables, were they cleaned well during replacement? If the corrosion was heavy, I've even seen the corrosion migrate into where cable meets lug terminal, even on molded terminals. Point is, a number of things can cause this, but is usually easy to find. You simply need a 12C test light probe. Hold the ground clamp end of the tester directly onto the neg post of the battery. Place the test needle of the test probe directly to the pos post of the battery, it should light the lamp in the tester. Have someone turn switch to engage starter. Does the lamp go out? If so, bad battery. If not, remain holding neg clamp to neg post, not lug terminal, move probe needle to pos post lug terminal, turn switch to start. Does lamp go out? If so, bad pos connection. If not, move ground clamp of tester to neg lug terminal. Try again. If light stays lit, move probe needle to cable connection to starter. If the lamp stays lit at this point, you need to check your grounds. Ground strap from motor to frame and ground cable from battery to frame. If all this checks ok, sounds like you have a starter problem.