Defective rebuilt starters are not unheard of. :angryfire
That said, the first thing to check would be the connections to the new starter. Also, assure that you have less than 0.5 ohm from the engine block to the battery "-" terminal, and that both battery terminals are tight.
If you didn't do the starter yourself, the shop should be willing to check it for you.