Also I suggest checking all your grounds. Both engine to frame and battery ground. Check the large hot wire to the starter as well. A corroded wire can sometimes hide inside the insulation of the wiring. A good digital multimeter is your friend here. The easiest way to check the main relay is the good ole "replace with known good" or "borrow a buddies" and slap it in. If you don't have access, google the testing procedure. I can't remember it off the top of my head but there are 203483204 threads on various forums with good info on testing the main relay. Also, just because the starter is "new" doesn't mean it is good. I have had bad starters right out of the box from places like autozone a billion times. Also, stick your meter leads into the neg and pos of the battery and see what kind of voltage drop you are getting when you attempt to start. If you are dropping excessive volts but not turning over the starter, than you have either a short or excessive resistance in either your supply or grounding wires.

oh, also, never ever overlook the keyswitch.