As 54TOW suggests, the battery power output is not enough to do what you want.
To plow old ground:
1. Are you absolutely sure the new battery is at full charge? Test it to make sure. Take the cables off and test the battery for voltage. If you get a drop in voltage as you are testing, then the battery has only a "top" charge which is not deep within the battery plates and acid. You battery needs a charge.
2. With the battery fully charged, is there anything that is "resisting" the current flow from the battery? This could be dirty connections at the battery or at the end of the battery cables. Dirt and grime = resistance, which will eat up all of the battery power going to the electrical system.
3. Old, worn internally frayed or broken wires inside the battery cable(s) will absolutely break or weaken the circuit. You may get just enough power (amps) through worn out wiring to make a few things work, sort of, like the horn, fuel gauge, maybe lights, but when you go for the gusto and mash the starter, then you are asking for more than the battery can deliver and----dead!
4. Somehting wrong with the starter itself. This is a little harder to figger, but my first question is (assuming you have a masher starter--one with the foot pedal), when you mash the foot pedal down slowly, do you meet with some pressure, or can you depress the pedal all the way with no resistance? Here's what you can do. Look at the lever that protrudes out of the starter motor housing while you have someone mash the pedal. If the linkage contacts that lever and requires further depression to make contact with that little button on the electrical switch atop the starter motor housing, then retracts to the rest position, the bendix and drive inside the starter motor is probably NOT locked up into the flywheel. But if that lever is resting in contact with the button on the electrical switch, then, yes, for some odd reason (like worn out springs internally within the starter motor, or a bent bendix drive, or....) then the starter may be locked up into the flywheel.
All that said, I would vote for corroded terminals, weak battery and such.
The fact that after the battery goes "dead" when you mash the starter pedal, but recovers some charge within a few minutes says that the big item (the starter motor) is quickly draining the battery. Once recover of some power happens, then the fuel gauge shows something--aha! there is some power again. Mash the starter and all the power goes away and the fuel gauge indicates empty. Battery power too low to do what you are asking.
