Your story is so classic, and I've heard it so many times. Forgive me, but I gotta ask---that new solenoid you just put in, is it the correct one, or did you go to the auto parts store and get a car solenoid that looks exactly alike? If you put in a car solenoid, take it back out and put the original back in, at least till you prove it is bad. And if you do prove it is bad, replace it with the correct type. If you have a car solenoid in there, you have two problems, the original problem, plus the incorrect solenoid problem.
OK, preaching is done now, so on to the question. Don't guess--test!! Do you have a voltmeter (multimeter) and do you know how to use it? Check the voltage on the two small posts on the solenoid while a helper turns the key to start. Should have battery voltage on one, and zero voltage on the other, and solenoid should click, and starter should run. By "voltage" I mean +tester lead on one post, - lead on ground
1. No voltage on either one, problem is ahead of there. Wires, key switch, battery, battery cables, etc.
2. Battery voltage on both, solenoid does not click-- Safety switch is shot OR safety switch is out of adjustment OR throttle is advanced beyond "start" position. BTW, if you had a car solenoid in there, you probably destroyed the safety switch.
3. Voltages are as they should be, but solenoid does not click-- solenoid is bad. (This scenario is very unlikely)
4. Voltages are as they should be, solenoid clicks, but starter does not run-- Solenoid is bad OR starter is bad, OR battery OR battery cables are at fault. Includes battery cables connections. Don't just look at them, take them off and clean them shiny bright and reinstall tightly.