Ditto on checking the ground cable, and the starter to engine block mounting area; the starter grounds via the starter case to the block (usually). Did you clean the paint off of the rebuilt starter? I usually buff the starter flange and where it meets the block, buff the block, and I then apply dielectric grease when I bolt the starter on.
If you have a voltage meter, you can isolate the battery cables, and check resistance in the cables themselves; you may have a bad cable. Sometimes only the cable ends, where the crimped connectors are, are the problem.
A good analog voltmeter is a good investment!
Best of luck!