Does the shutdown solenoid stay up when you pick it up manually with the switch on? If it does, the hold in coil is OK and your problem is no voltage to the pickup coil.
Check the fusible link. It is a blue 16 gauge wire from the battery on the driver's side that provides pickup power to the solenoid. If it is not burned, the connection may be bad at the battery. If it is burned you need to find out why. Usually caused by starter contacts sticking.
Be aware that there are two relays involved. One is the engine starter relay in the distribution center. It supplies voltage for both the starter solenoid and the fuel shutdown relay. It is apparently OK since the starter is working.
The other is the fuel shutdown relay located on the engine firewall.
Is this the one you replaced?