The first place I'd start is removing, cleaning, and reattaching the battery cables. Likely not a problem if you just put in a new battery.
Look for something not set right, like the PTO switch on.
Double check that the battery is good. Has been known that a new battery can have a dead cell, or not be charged enough in the beginning.
Lastly, if still not finding the problem, start tracing the 12v supply to see that it is getting from the battery to the solenoid, and that the solenoid is getting 12v from the ignition switch.