If you have a multi-meter, check to see if you have power getting to the battery side of the solenoid. If you do, then it's not the relay. (You may have to turn the key on to check this, as the relay needs to be engaged)
If no power to solenoid, then pull the relay, switch it with another relay in the box (same type) and see if the starter works that way. If so, then you do have a bad relay.
But before anything, remove and clean the battery cables and terminals, and trace your ground to the frame and remove and clean that. Many times it's just a bad connection on the battery terminals, or the ground.
Edit: Also, do you have dash lights come on when you turn the key on?