You have one of three problems.
1. the new solenoid is no good
2. you have a poor connection somewhere between the solenoid and the starter.
3. your new starter is bad.

To make each of the following checks you have to turn the key to the "START" position for each test.
With a volt meter you can find out wher the problem is. Put the red lead form the volt meter on the battery side of the solenoid and the black lead on the starter side of the solenoid. Try to start the car. if you have more than 0.5 volts reading on the voltmeter your solenoid is bad. Replace it. If it is less than 0.5 volts then move the red lead of the meter to the starter side of the solenoid and the black lead to the starter terminal on the starter. (one lead on each side of the starter cable) If you have more than 0.5 volts the wire is bad. Replace it. If it is less than 0.5 volts then move your red lead to the starter terminal on the starter and the black lead to the engine block where you can get a good connection. If the voltmeter reads more than 0.5 volts then your starter is bad. If it reads less than 0.5 volts then put the red lead on the engine block and the black lead on the car frame or body somewhere there is a good connection. If it reads more than 0.5 volts then you need a ground strap. Install one - a BIG one from the engine to the frame. If it is less than 0.5 volts then put the red lead on the frame and the black lead on the negative battery cable (not the post) If the meter reads more than 0.5 volts then the battery negative cable is bad. Replace it. If it reads less than 0.5 volts then move the red lead to the negative battery cable clamp and the black lead to the battery negative post. If the voltage is more than 0.5 volts then the cable clamp is bad. replace the negaive battery cable - do not try to install a new clamp or use a clamp on battery terminal. If it is less than 0.5 volts then check the volts from the positive terminal to the negative terminal. If you have more than 9.5 volts then you have missed something and you need to go over it again. If the voltage is less than 9.5 volts then you either need to charge the battery or replace it.

It took longer to read this (and type it) than it does to do it. You can be sure of the results without replacing anything before you know what is wrong.

______________________________________
Paul
______________________________________
retired mechanic after 35 years
specialized in Holley carbs and Ford Automatic Transmissions