Make sure both ends of each battery cable and the engine to chassis strap is clean and secure. Check the battery cables for corrosion. Corrosion can occur under the insulation.
Make sure all connections to the starter are clean and secure.
Use a meter to check the battery. New parts aren't always good parts.
Where did you get the starter from? Most chain autoparts stores will test the starter for free.
Clicking noise is indicative of low voltage, bad connections, high resistant connections.
Below is a thread refering to a similar problem.
http://www.automotiveforums.com/vbul...d.php?t=610154